목록퀵정렬 (3)

프린세스 다이어리

[C] 퀵 정렬이란? C언어로 퀵 정렬 구현하는 코드

1. 퀵 정렬이란 퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는 데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로, 평균적으로 0(NlogN)의 시간 복잡도를 가진다. 퀵 정렬은 편향된 분할이 발생할 때 연산의 양이 최악의 경우 O(N2) 이다. 따라서 실제로 정렬할 때는 퀵 정렬을 굳이 직접 구현하지는 않는다. C++에 Algorithm 라이브러리에 포함된 sort() 함수는 퀵 정렬을 기반으로 하면서 O(NlogN)을 보장한다. 피벗 값이 가장 왼쪽이라고 가정한다. 5 4 3 8 9 6 7 1 10 2 (1) 5의 왼쪽부터 시작해서 5보다 큰 값을 찾는다. 또 오른쪽부터 시작해..
C, C++ 2021. 11. 10. 22:13
[프로그래머스] 가장 큰 수 문제 자바스크립트 풀이

> 문제 바로가기 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 1. 접근 방법 (1) 조건을 충족하는 방식으로 compare하는 함수를 만든다. const isLeftBiggerThanRight = (left, right) => { if ((String(left) + String(right)) >= (String(right) + String(left))) { return true; } else { return false; } } (2) 퀵 정..
자료구조, 알고리즘 2021. 11. 1. 12:02
자바스크립트 핵간단한 퀵정렬 코드

퀵 정렬은 정렬 알고리즘이다. 선택 정렬보다 훨씬 빠르고 실제로도 많이 사용된다. C언어 표준 라이브러리에는 qsort라는 함수가 있는데 이것이 바로 퀵 정렬을 구현한 함수다. 퀵 정렬은 분할 정복 전략 중에 하나다. 배열을 정렬할 때 가장 간단하고 연산이 적은 배열은 무엇일까? 바로 정렬할 필요도 없는 배열이다. [] (비어 있는 배열) [5] (원소가 하나인 배열) 비어 있는 배열이나 원소가 하나인 배열이 기본 단계가 된다. 이 경우, 배열을 있는 그대로 반환하면 된다. function quickSort(arr) { if (arr.length
자료구조, 알고리즘 2021. 10. 31. 19:44
Prev 1 Next