Prosto

'빠르게 정렬하는 방법으로 가장 많이 사용되는 퀵정렬' 퀵 정렬은 빠른 정렬이나 퀵 소트(Quick Sort)라고도 부릅니다. 퀵 정렬(Qucik Sort)는 데이터를 정렬하는 방법 중 하나입니다. 데이터를 분할(Divide)하고 분할된 부분 별로 이동하는 정복(Conquer) 과정을 반복하여 거쳐 정렬하는 방법입니다. (지금까지의 정렬들과 달리 조금은 복잡합니다만 보고, 직접 해보며 이해할 수 있을 겁니다.) 성능을 Big O로 표기한다면 average, best = O(n log n)이고, worst = O(n^2)입니다. 일반적으로는 O(n log n)의 성능을 내주지만, 피봇(중심점이) 항상 최솟값이나 최댓값으로 잡힌다면 최악의 성능인 O(n^2)이 나옵니다. 참고로 지금까지 했던 (선택, 삽입,..

'맞는 위치에 삽입시켜가며 정렬하는 삽입정렬' 삽입정렬은 Insertion Sort라고도 부르며 데이터 정렬 방법 중 하나입니다. 키(key) 값을 가지고 정렬시키는 삽입 정렬은 두 번째 자료부터 시작하여 그 앞의 자료들과 비교하여 알맞은 위치로 삽입하는 형태의 정렬입니다. (배열로 보는 경우 삽입이라면 뒤의 자료들은 한 칸씩 밀리는 형태가 되겠죠?) (아래 데이터 이동 그림을 보시면 이해하시기 더 좋을 것이라 생각됩니다.) 여러 회전을 반복하여 정렬하는 방법입니다. 첫 번째 회전에서는 두 번째 자료를 키 값으로 가지고 앞의 자료들을 하나씩 비교합니다. 두 번째 자료의 앞 자료는 첫 번째 자료 하나밖에 없으니 하나만 확인하면 됩니다. 첫 번째 자료가 키 값보다 크다면 두 번째 자료를 첫 번째 자료로 바꿔..

'선택하여 차례대로 정렬하는 선택정렬' 선택 정렬은 데이터를 정렬하는 방법 중 가장 기본적인 방법으로 첫 번째 자료부터 마지막 자료까지 하나씩 순서대로 정렬해가는 방식입니다. 오름차순이라면 가장 낮은 숫자가 첫 번째, 가장 높은 숫자가 마지막이 되겠죠? (내림차순이라면 그 반대의 결과가 나오겠죠?) 그렇다면 이 선택 정렬은 어떻게 이루어지는 걸까요? 오름차순을 기준으로 이야기하자면 이렇습니다. 첫 번째 위치인 가장 낮은 값을 찾기 위해서 두 번째부터 마지막까지 낮은 값을 확인하여 첫 번째 값을 결정합니다. 그 과정에서 현재 위치의 값보다 작은 값을 만나면 서로의 값을 교환해줍니다. 그 후 두 번째로 낮은 수를 찾기 위해서 세 번째부터 마지막까지 현재 두 번째 자리의 수보다 낮은 값이 있는지 확인하죠. 마..