<버블정렬>
모든 요소를 앞에서부터 2개씩 비교해서 제일 큰 수를 맨 뒤로 보낸 후,
나머지 요소들로 반복작업을 통해 작업을 수행하는 정렬방식.
- 시간 복잡도 : O(n^2) -
10개의 요소를 가진 A배열이라 한다면, 10 + 9 + 8 + 7 .....+1 이렇게 값을 비교하게 되는 등차수열을 가지게 된다.
n(n+1)/2 이니깐 시간 복잡도는 n**2
1. BubbleSort 슈도코드
입력 : 크기가 n인 배열 A
출력 : 정렬된 배열 A
1 for pass = 1 to n-1
2 for i = 1 to n-pass
3 if(A[i-1]> A[i]) // 위의 원소가 아래의 원소보다 크면
4 A[i-1] <ㅡ> A[i] // 서로 자리를 바꾼다.
5 return 배열 A
<직관적 설명>
1. 값들을 둘씩 비교하면서 가장 큰 수를 맨 뒤로 보낸다.
2. 가장 큰 수를 빼고 나머지 수들을 다시 둘씩 비교한다.
3. 위 과정을 둘씩 비교가 안될 때까지 반복한다.
<특징>
1.안정적 정렬이다.
2.첫 번째 패스가 수행된 후에는 가장 큰 숫자가 배열의 마지막 원소에 자리 잡는다.
<선택 정렬>
모든 요소들에서 가장 작은 값을 고른 후, 계속 작은 값으로 선택되지 않는 값들 중, 가장 작은 값을 뽑는 정렬방식
시간복잡도 : O(n^2)
마찬가지로 가장 작은 값을 고른 후, 계속 남은 값에서 작은 값을 뽑아내주니
등차수열의 모양새가 된다. 그래서 n^2의 시간복잡도를 가진다.
1. SelectionSort 슈도코드
입력: 크기가 n인 배열 A
출력: 정렬된 배열 A
1 for i = 0 to n-2 {
2 min = i
3 for j = i+1 to n-1 { // A[i]~A[n-1]에서 최솟값을 찾는다.
4 if(A[j]<A[min])
5 min = j
}
6 A[i] <ㅡ> A[min] // min이 최솟값이 있는 원소의 인덱스이다.
}
7 return 배열 A
<특징>
1. 비안정적 정렬이다.
2. 입력에 민감함이 없기 때문에 대용량의 입력에 대해서도 우수한 성능을 보인다.
<삽입 정렬>
앞의 요소들에서 뒤의 1개의 요소가 들어갈 적절한 위치를 찾는 정렬방식.
적절한 위치란, 삽입할 요소를 앞에서 정렬된 요소들과 하나씩 비교해보는 것.
삽입이 정렬된 요소들 중 앞에서 되었다면 뒷 쪽과는 비교가 필요하지 않기에
계산이 좀 더 빨라진다.
InsertionSort 슈도 코드
입력: 크기가 n인 배열 A
출력: 정렬된 배열 A
1 for i = 1 to n-1 {
2 CurrentElement = A[i] // 정렬이 안 된 부분의 가장 왼쪽 원소
3 j <ㅡ i - 1 // 정렬된 부분의 가장 오른쪽 원소로부터 왼쪽 방향으로 삽입할 곳을 탐색하기 위하여
4 while (j >= 0) and (A[j]>CurrentElement) {
5 A[j+1] = A[j] // 자리 이동
6 j <ㅡ j - 1
}
7 A[j+1] <ㅡ CurrentElement
}
8 return A
시간 복잡도 : O(n^2)
다른 버블, 선택정렬보다는 빠른 편이다. 하지만 가장 오래 걸릴 경우, 등차수열의 모양을 보임으로
시간 복잡도는 n^2이다.
거의 정렬된 상태에서는 다른 알고리즘보다 가장 효율적일 수 있다.
예시를 직접 그려보았다.
뒤에서 부터 차근차근 하나씩 비교하는 모습 확인 가능.
정렬된 앞 부분과 정렬되지 않는 뒷부분 중 뒷부분 재정렬할게 없다면 모든 값들을 서로 비교하는 것 없이
바로 종료 가능하다.
만약 모두 정렬되어 있다면 가장 빠른 시간 복잡도 n-1(O(n)) 을 보일 것이고,
역정렬 되어 있는 상태라면 n^2의 시간이 걸릴 것이다.
<특징>
1. 안정적 정렬이다.
2. 거의 정렬되어 있는 입력에 대해 가장 짧은 수행시간을 가진다.
(이미 정렬되어 있는 부분을 이용해 새로운 원소를 삽입하기 때문)
'📈알고리즘 > 알고리즘' 카테고리의 다른 글
| 유전자 알고리즘 이해해보기 (0) | 2023.05.17 |
|---|---|
| 쉘 정렬 , 힙 정렬, 정렬 문제의 하한 (0) | 2023.05.08 |
| 배낭문제 Knapsack (0) | 2023.04.24 |
| 편집 거리 문제(Edit distance) (0) | 2023.04.20 |
| 연속 행렬 곱셈 (0) | 2023.04.18 |