Sort5 [Sort] Bucket Sort 이번 글은 bucket sort를 다뤄보겠습니다. 아마 생소할 지도 모르겠네요.Bucket sort는 non-comparision sort로 먼저 소개했었습니다.차차 과정을 보면서 설명하겠지만 이 정렬은 이름대로 바구니를 사용하는 정렬이라고 생각하면 좋을 것 같습니다. Bucket sort는 크게 세 단계가 있습니다. 1. key를 bucket 안에 넣는다.- 이때 bucket은 key들의 특정한 공통점을 말합니다. 예를 key가 같거나, 자릿수가 같거나, 어떠한 범위가 될 수도 있습니다.2. bucket 정렬이 필요하면 bucket을 정렬한다. 그리고 bucket 안의 key를 정렬한다.3. 정렬된 모든 key를 모은다.이렇게 하면 정렬된 배열을 얻을 수 있습니다. 코드를 통해 알아봅시다.이 코드는 .. 2025. 4. 24. [Sort] Insertion Sort Insertion Sort도 유명한 정렬 중 하나이죠.Insertion Sort는 k번째 탐색과정에서 k번째로 작은 요소를 그 앞 배열에 적절한 위치에 삽입하는 것입니다.즉, 각 과정에서 요소는 자신의 위치까지 앞에 있는 요소와 교환되는 것입니다.그림을 보면 이렇게 변경됩니다.화살표로 요소들이 swap되는 것을 볼 수 있습니다. 그럼 반복문을 통해 코드를 구현해 볼까요.void insertionSort(int list[], int n) { cout " =0 && list[j]>key ) { cout " 이번에는 swap 말고 move라고 표현해봤습니다.k번째 요소를 key로 두고 그 앞의 요소를 뒤로 한 칸씩 미룬 뒤에, key를 삽입하는 방법입니다. 결과는 이렇게 나옵니다... 2025. 4. 22. [Sort] Selection sort 이번 글에서는 selection sort를 정리해봅시다.Selection sort는 각 단계마다 가장 작은 key를 찾아서 적절한 위치에 넣는 정렬입니다.위의 그림을 보면 각 단계별로 바뀌는 배열을 볼 수 있습니다. 매우 직관적인 방법이죠.설명보단 바로 코드를 봐볼까요 void selectionSort(int list[], int n) { cout " 코드를 살펴봅시다. 1. 먼저 각 단계마다 배열에서 최소값을 구합니다.for (int i=0; i 2. 그리고 최소값이 들어갈 위치에 있는 값과 최소값을 교환합니다.int temp = list[i]; list[i] = list[min_index]; list[min_index] = temp; 그럼 결과를 확인해 볼까요 응용.. 2025. 4. 21. [Sort] Bubble sort 첫 번째로 가져온 건 bubble sort 입니다.Bubble sort는 정렬되는 모습이 수면 위로 올라오는 거품과 비슷해 붙여진 이름입니다.그림을 보면 다음과 같습니다.각 pass에서 작은 key가 점차 올라오는 것을 볼 수 있습니다.인접한 key를 비교하여 바꾸는 방법으로 정렬됩니다. 이 방법은 작은 key부터 왼쪽으로 정렬하는 반면,큰 key부터 오른쪽으로 정렬하는 방법도 있습니다.그 2가지 경우의 코드를 모두 봐보겠습니다. - 작은 key부터 왼쪽으로 정렬// list: given unsorted array, n: number of elementsvoid bubbleSort_ver1(int list[], int n){ cout " i; j--) { if (list[j] .. 2025. 4. 21. [Sort] Intro 오랜만에 글을 쓰러 왔습니다. 왜냐면 그동안 바빴다가 휴학을 했기 때문이죠. 휴학하면서 배웠던 내용도 정리하고, 코딩을 꾸준히 해서 실력을 높여보려 합니다. 오늘은 정렬을 가져와봤습니다.1. 정의정렬(sort)은 요소(element)들을 특정 기준에 따라 재배열하는 것입니다.각각의 요소는 (key, info)로 주어집니다.대표적인 것은 숫자와 문자의 정렬이 있습니다. 이들은 보통 내림차순, 오름차순으로 정렬됩니다. 2. 분류1) Memory usageInternal(In-memory) sort$ O(n^2) $ : bubble sort, selection sort, insertion sort$ O(n log{n}) $ : heap sort, quick sort, mergy sortExternal sort.. 2025. 4. 17. 이전 1 다음
