소스 보기

참여 링크 - https://meet.google.com/ytw-nkkt-zzr

주제 소개

정렬이란? 정렬(sorting)은 이름，학번, 키 등 핵심 항목(key)의 대소관계에 따라 데이터 집합을 일정한순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다

단순 정렬

가장 단순한 정렬 중 삽입 정렬과 선택 정렬이 있으며 이 둘 모두 낮은 부하로 인해 작은 데이터에 효율적이지만 큰 데이터에는 효율적이지 않다.

효율 정렬

실용적인 일반 정렬 알고리즘들은 평균 시간 복잡도(및 일반적으로 최악의 경우의 복잡도) O(n log n)의 알고리즘에 기반한 경우가 대부분이며 그 중 가장 흔한 것이 힙 정렬, 합병 정렬, 퀵 정렬이다

선택 정렬

아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택
a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환

for(int i = 0; i < n - 1 ; i++) {
	// min = a[i] ~ a[n - 1] 에서 가장 작은 값을 가지는 요소의 인덱스
	// a[i] 와 a[min] 의 값을 교환

삽입 정렬

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

주어진 배열 중에서 최솟값 또는 최댓값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.

for (int i =1; i <n; i++) {
		A[1...last] 중 가장 큰 수 A[k]를 찾는다
        A[K] = A[last]; A[k]와 A[last]값을 교환
}

합병 정렬

리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

mergeSort(A[],p,r){
    if(p<r) then{
        q = (p+r)/2;
        mergeSort(A,p,q);
        mergeSort(A,q+1,r);
        merge(A, p, q, r);
    }
}

merge(A[], p, q, r){
    정렬되어 있는 배열 A[p..q]와 A[q+1...r]을 합하여
    정렬된 하나의 배열 A[p...r]을 만든다.
}

SLS > 2주차. Sorting And String Manipulation > 스크린샷 2020-08-11 오후 5.30.12.png