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)이 나옵니다. 참고로 지금까지 했던 (선택, 삽입,..

'검색할 범위를 반으로 줄여가며 찾아가는 이분 검색(Binary Search)' 이분 검색은 검색할 자료를 반씩 나누어 나머지 반만 검색하는 방식을 반복하여 자료를 찾는 검색(탐색) 방법입니다. 이 이분 검색을 이용하여 자료를 찾는다면 빠른 속도로 원하는 자료를 찾을 수 있습니다. (단, 이분 검색은 정렬되어있는 데이터에 사용할 수 있습니다.) (정렬 방법은 블로그 내의 다른 글을 참고하시면 도움이 될 것 같습니다.) 성능을 Big O로 표기한다면 O(log n)입니다. 자료가 2개라면 1번, 4개(2^2개)라면 2번, 8개(2^3개)라면 3번, 16개(2^4개)라면 4번, ... 1,024개(2^10개)라면 10번, 1,048,576개(2^19개)라면 최대 19번이면 찾습니다. 굉장히 빠르죠? 실제 배..

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

'보글보글 거품 같이 차례차례 정렬하는 버블정렬' 버블정렬은 거품정렬이나 버블소트(Bubble Sort)라고도 부릅니다. 버블정렬은 데이터 정렬을 하는 방법 중 하나입니다. 첫 번째 자료와 두 번째 자료, 두 번째 자료와 세 번째 자료, 세번째와 네 번째 자료를 비교하는 식으로 정렬을 진행합니다. (아래 그림 보시면 이해가 빠를 겁니다.) 여러 회전을 반복하여 정렬하는 방법입니다. 첫 번째 회전에서는 첫 번째 자료와 두 번째 자료를 비교하여 첫 번째 자료가 더 큰 경우 첫 번째와 두 번째 자료를 바꿉니다. (두 번째가 더 큰 경우는 안 바꿈 ) 그리고 두 번째 자료와 세 번째 자료를 비교하여 위와 같은 작업을 해줍니다. 마찬가지로 세 번째와 네 번째, 그렇게 마지막 자료까지 비교해줍니다. (그렇다면 결과..

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