공부 정리

* Counting Sort? 카운팅 소트는 일단 한 수가 몇번 등장하는지를 세는 것에서부터 시작을 한다. 그런다음 누적합을 구해준다. 이게 무슨 소리냐면 0번이 2번, 1번이 2번 나왔다면 누적합 배열에서는 2번 나온 0이 2, 그 다음인 1이 2+2해서 4가 된다는 얘기다. 카운팅 소트의 핵심은 앞의 놈이 몇번 나왔는지 안다면 나는 몇번부터 몇번 인덱스에 걸쳐있을지를 계산할 수 있다는 것이다. * Pseudocode CountingSort(A) //A[]-- Initial Array to Sort //Complexity: O(k) for i = 0 to k do c[i] = 0 //Storing Count of each element //Complexity: O(n) for j = 0 to n do ..

* Quick Sort? 퀵 정렬도 합병 정렬과 같이 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 분할정복법에 근거한다. 그러나 합병 정렬은 전체 데이터를 n/2로 나눴던 것과 달리, 퀵소트는 비균등하게 분할한다. 리스트 안에 있는 한 요소를 기준(피봇(pivot))으로 선택한다. 피봇을 중심으로 왼쪽은 피봇보다 작은 요소들로 옮겨지고, 오른쪽은 피봇보다 큰 요소들로 재구성되게 된다. 이 상태에서 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 재정렬하게 되면 전체 리스트가 정렬된다. 퀵 정렬 함수는 부분 리스트에 대하여 순환 호출 된다. 부분 리스트들이 더 이상 분할이 가능할 때까지 피봇을 기준으로 2개의 부분 리스트로 재분할되는 것이다. 그러니까 퀵 소트는 피봇을..

* Merge Sort? 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 방식이다. 합병 정렬은 분할 정복(divide and conquer) 기반이라고 볼 수 있다. 합병 정렬은 다음의 단계들로 이루어진다. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합한다. * Pseudocode 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(m..

* Shell Sort? 쉘 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 1. 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 2. 모든 부분 리스트가 정렬되면 쉘 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이한다. 3. 부분 리스트의 개수가 1이 될 때까지 이 과정을 반복한다. 부분 리스트를 만들 때에는 주어진 리스트의 k번째 요소를 추출하여 만든다. 이 k번째 요소를 간격(gap)이라고 한다. 이 간격은 처음에는 자료의 개수가 n개 있다면 n / 2 정도로 정하고 각 패스마다 간격을 절반으로 줄이는 방식을 많이 사용한다. * Pseudocode * 분석 삽입..

* Insertion sort? 삽입 정렬은 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다. 이와 같은 작업을 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. 이와 같이 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. * Pseudocode * 분석 복잡도는 자료 구성에 따라서 달라진다. 입력 자료가 정렬되어 있다면 가장 빠르다. 삽입 정렬의 외부 루프는 n-1번 실행되며 각 단계에서 1번의 비교와 2번의 이동만 이루어지므로 총 비교 횟수는 n-1번, 총 이동 횟수는 2(n-1)번이 되어 알고리즘의 시간 복잡도는 O(n)이다. 최악의 복잡도는 입력 자료가 ..

* Bubble Sort? 버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 버블 정렬을 오름차순으로 한 번 실행하였다면, 리스트의 가장 오른쪽 끝에는 제일 큰 수가 들어가게 된다. 오른쪽부터 정렬이 완료되며 정렬이 되지 않은 왼쪽을 반복하여 정렬하면 정렬이 완료된다. * Pseudocode 하나의 스캔은 index = 0 부터 index = i - 1 까지 반복하는 루프로 구성된다. index 번째 요소와 index + 1 번째 요소를 비교하여 둘이 크다면 swap 한다. 이러한 스캔 과정이 n - 1번 반복되면 정렬은 완료된다. * 분석 버블 정렬의 비교 횟수는 항상 최선, 평균, 최악..

* Selection Sort? 선택 정렬은 입력 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 이 절차를 (숫자 개수 - 1)만큼 되풀이하면 전체 숫자들이 정렬된다. * Pseudocode * 분석 선택 정렬은 2중 for문을 돌게 된다. 외부 for문은 n-1번 시행되며, 내부 for문은 0부터 n-2까지 변하는 i에 대하여 (n-1-i)번 반복 수행될 것이다. 실제 비교는 내부 for문에서 수행되는데 i가 0일 떄 n-1번, i가 1일 떄 n-2번 이런 식으로 비교하니까 총 비교 횟수는 (n -1) + (n - 2) + ... + 1 = n ( n + 1) / 2..