선택정렬, 삽입정렬
1. 선택정렬
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
1.1 정렬과정
- 주어진 배열 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다. (pass)
- 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
1.2 코드
1.2.1 Java
void selectionSort(int[] arr) {
int indexMin, temp;
for (int i = 0; i < arr.length-1; i++) { // 1.
indexMin = i;
for (int j = i + 1; j < arr.length; j++) { // 2.
if (arr[j] < arr[indexMin]) { // 3.
indexMin = j;
}
}
// 4. swap(arr[indexMin], arr[i])
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
System.out.println(Arrays.toString(arr));
}
1.2.2 Python
def selection_sort(a):
size = len(a)
for i in range(size):
minidx = i
for j in range(i+1,size):
if(a[minidx]>a[j]):
minidx=j
a[minidx],a[i] = a[i],a[minidx]
arr = [9,1,22,4,0,-1,1,22,100,10]
selection_sort( arr )
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]
1.3 복잡도
1.3.1 시간복잡도
데이터의 개수가 n개라고 했을 때,
-
첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
-
두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
...
-
(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
따라서 최선, 평균, 최악의 경우 시간 복잡도는 O(n^2)
1.3.2 공간복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.
1.4 장단점
-
장점
-
Bubble sort와 마찬가지로 알고리즘이 단순
-
Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
=> 제자리 정렬(in-place sorting)
-
-
단점
- 불안정 정렬(Unstable Sort)
2. 삽입정렬
모든 요소를 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하여 정렬을 완성하는 알고리즘
2.1 정렬과정
- 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
- temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
- '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.
모든 요소를 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하여 정렬을 완성하는 알고리즘
2.2 코드
2.2.1 Java
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){ // 1.
int temp = arr[index];
int prev = index - 1;
while( (prev >= 0) && (arr[prev] > temp) ) { // 2.
arr[prev+1] = arr[prev];
prev--;
}
arr[prev + 1] = temp; // 3.
}
System.out.println(Arrays.toString(arr));
}
2.2.2 Python
def insertion_sort(arr):
for i in range(1, len(arr)) :
j = i-1
temp = arr[i]
while j>=0 and arr[j]>temp :
arr[j+1] = arr[j]
j-=1
arr[j+1] = temp
arr = [9,1,22,4,0,-1,1,22,100,10]
insertion_sort(arr)
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]
2.3 복잡도
2.3.1 시간복잡도
-
최악의 경우
- (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
- 즉, O(n^2)
-
최선의 경우
- 이미 정렬이 되어 있는 경우
- 한번씩 밖에 비교를 안하므로 O(n)
2.3.2 공간 복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.
2.4 장단점
-
장점
-
대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적
-
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)
-
안정 정렬(Stable Sort) 이다.
-
선택정렬이나 거품정렬와 같은 O(n^2)이지만, 상대적으로 빠르다.
-
삽입정렬은 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행됨.
선택정렬의 경우 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색해야함
-
-
단점
- O(n^2) 이라 느림
Author And Source
이 문제에 관하여(선택정렬, 삽입정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@swhan9404/선택정렬-삽입정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)