[알고리즘] 정렬

Selection sort

가장 큰 값을 가지고 맨 마지막에 합니다. 그 다음에 계속 확인하면서 반복을 합니다. 마지막에 간 값은 다시 확인하지 않아도 됩니다. 나머지에도 똑같은 일을 계속 반복해주면 됩니다.

 

다섯개 값에 마지막 값을 하나 추가했다면 네개의 값에서 가장 큰 값과 4번째 인덱스를 바꿔줍니다. 이렇게 계속 반복해줘서 해주는 것이 선택 정렬입니다. 

 

selectionSort(A[], n)
{
	for last <- n downto 2 {
    	A[1...last] 중 가장 큰 수 A[k]를 찾는다;
        A[k] <-> A[last]; 
    }
}

실행시간:

• for 루프는 n-1번 반복
• 가장 큰 수를 찾기 위한 비교 횟수 n-1, n-2 ,,... , 2, 1
• 상수 작업 시간 작업 

시간복잡도 t(n) = n-1  + n-2 + ... 2 + 1 = O(n^2)

 

bubble sort

정렬할 데이터 중에서 가장 큰 값을 찾아 맨 마지막으로 옮긴 다음 그 데이터를 잊어버리고 나머지 데이터에 대해서 계속 반복하도록 합니다. 

 

실행시간은 Selection sort와 똑같이 O(n^2)이 됩니다. 세부적인 방법만 조금 차이가 날 뿐입니다. 

 

bubbleSort(A[], n)
{
	for last <- n downto 2{
    for i <= 1 to lst-1
    	if(A[i]>A[i+1]) then A[i] <-> A[i+1];
}

수행시간

1. for 루프는 n-1번 반복
2. for 루프는 각각 n-1, n-2 , ... , 2, 1번 반복
3. 교환은 상수시간 작업

T(n) = O(n^2)

 

Insertion Sort 

삽입 정렬(Insertion Sort)은 각 요소를 적절한 위치에 삽입하여 정렬하는 알고리즘입니다. 기본적인 흐름은 다음과 같습니다.

먼저, k-1개의 데이터가 이미 정렬되어 있다고 가정하고, k번째 데이터를 적절한 위치에 삽입하여 정렬 상태를 유지하는 과정을 반복합니다. 즉, 새로운 요소를 추가할 때마다 기존의 정렬된 부분에서 올바른 위치를 찾아 삽입하는 방식입니다

.

삽입 위치를 찾는 과정에서, 앞에서부터 탐색하며 삽입할 값보다 큰 값이 나타나는 순간, 해당 값의 앞이 적절한 삽입 위치라고 판단합니다. 하지만 배열을 사용하기 때문에 삽입 이후의 요소들은 한 칸씩 뒤로 밀려야 합니다.

 

따라서, 효율성을 높이기 위해 뒤에서부터 비교하는 방식이 더 적절합니다. 예를 들어, 삽입할 값이 4라면 4보다 작은 값들은 검사를 하지 않아도 되므로, 뒤에서부터 4보다 큰 값들을 한 칸씩 뒤로 이동시키는 방식이 효과적입니다.

 

구체적인 과정은 다음과 같습니다. 삽입할 값을 임시 변수에 저장한 후, 해당 값을 기준으로 앞의 요소들과 비교하면서 한 칸씩 뒤로 이동시킵니다. 그러다가 삽입할 값보다 작은 값이 나타나면, 그 위치에 삽입하여 정렬 상태를 유지합니다.

 

이러한 과정을 반복하면 최종적으로 모든 요소가 정렬된 상태가 됩니다.

 

insertionSort(A[], n)
{
	for i <- 2 to n
    {
    	A[1...i]의 적당한 자리에 A[i]를 삽입한다.
    }
}

수행시간

• for 루프는 n-1번 반복
• 최악의 경우 i-1번 비교 

(n-1) + (n -2) + ... + 2 + 1 = O(n^2)