[Algorithm] 정렬 알고리즘에 대하여 1

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

이번 포스트에서는 기본적인 정렬 알고리즘에 대해 포스팅하겠습니다.

 

 

 

대표적인 정렬 알고리즘

버블 정렬(bubble sort)

코드

void bubbleSort() {

}

맨 앞쪽 두 요소씩 값을 비교하며 정렬해 나간다. 마지막 요소는 최대값이 된다.

모든 요소가 정렬될 때까지 반복한다.

 

시간 복잡도

• 두 요소를 비교하는 횟수 : n-1, n-2, ..., 2, 1
• 두 수를 교환하는 횟수 : 1 * n (교환 여부를 예측할 수 없음)

T(n) = (n-1) + (n-2) + ... + 2 + 1 + 1 = n(n-1)/2 = o(n^2)

• 최악 : o(n^2)
• 최선 : o(n^2)
• 평균 : o(n^2)

 

 

삽입 정렬(insertion sort)

코드

void insertionSort() {

}

두번째 요소를 선택한다. 해당 요소 앞쪽으로 전진하면서, 적절한 위치에 삽입한다. (이 때, 각 요소들과 비교를 해야 하며, 적절한 위치가 아니라면 해당 요소를 뒤로 한칸씩 밀어야 한다.)

첫번째, 두번째 요소는 정렬이 되었으므로, 세번째 요소를 선택한 후, 앞쪽에 적절한 위치에 삽입한다.

모든 요소가 적절한 위치에 삽입될 때까지 반복한다.

 

시간복잡도

• 적절한 곳에 삽입 할 요소를 선택하는 횟수 : 1, 1, ..., 1
• 적절한 곳에 삽입하기 위해 이전 요소들과 비교하는 횟수 : 1, 2, ..., n-1 (최악의 경우)
• 적절한 곳에 삽입하기 위해 이전 요소들과 비교하는 횟수 : 1, 1, ..., 1 (최선의 경우)

T(n) = 1 + 2 + ... + n-2 + n-1 + 1 = n(n-1)/2 = o(n^2)

• 최악 : o(n^2)
• 최선 : o(n)

 

 

선택 정렬(selection sort)

코드

void selectionSort() {

}

첫번째 원소부터 가장 큰 값을 찾은 후, 맨 마지막 원소와 자리를 바꾼다. 맨 마지막 요소는 최대값이 된다.

모든 요소가 정렬될 때 까지 반복한다.

 

시간 복잡도

• for문 내에서, 마지막 요소를 고르는 횟수 : 1, 1, ..., 1
• for문 내에서, 가장 큰 수를 찾기 위한 비교 횟수 : n-1, n-2, ..., 2, 1
• 두 수를 교환하는 횟수 : 1 * n (교환 여부를 예측할 수 없음)

T(n) = (n-1) + (n-2) + ... + 2 + 1 + 1 = n(n-1)/2 = o(n^2)

• 최악 : o(n^2)
• 최선 : o(n^2)
• 평균 : o(n^2)

 

 

힙 정렬(heap sort)

3편에서..

 

기수 정렬(radix sort)

3편에서..