생각을 개발하자, 박진형

[자료구조 알고리즘] 자료구조 효율적인 탐색을 위한 정렬알고리즘#1 본문

Javascript/data structures

[자료구조 알고리즘] 자료구조 효율적인 탐색을 위한 정렬알고리즘#1

imjinbro imjinbro 2017.11.11 00:53

[정렬]

- 자료구조 연산 : 삽입 - 삭제 - 탐색(정렬되어있는 상태로)

- 탐색을 위한 정렬 : 탐색을 효율적으로 하기위해서



[버블정렬]

1) 구현하기는 쉽지만 데이터 개수가 늘어남에 따라 연산 횟수도 늘어남

2) N개의 데이터에서 순서대로 2개씩 잡고 오름/내림차순(비교와 이동 연산) 따라 정렬함

3) 공간복잡도 O(N) : 같은 배열에서 진행하기때문에

4) 시간복잡도 - 워스트 케이스

- 비교했을 모두 이동함

- 어쨌든 비교를 데이터 개수만큼 해야하고 비교를 어떻게 하나 : (n-1) + (n-2) + ...... + 1

- 등차수열의 : n(n-1)/2 -> O(N^2)

static void sort(int[] arr){
int length = arr.length;

for(int i=0; i<length; i++){
for(int j=1; j<length; j++){
/* 연산 : 비교 */
if(arr[j-1] > arr[j]){
/* 연산 : 이동 */
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}



[선택정렬]

- 구현하기는 쉽지만 데이터 개수가 늘어날 때마다 연산해야하는 횟수가 증가량이..

- 1 자리에 어떤 값을 넣어야하는데, 그것을 배열 끝까지 돌면서 찾기 : 자리에 맞는 값을 선택해서 정렬시킴

- 시간복잡도 : 비교 연산

(1) 워스트케이스 : 자리에 위치할 데이터가 끝에 있는 경우

(2) (n-1) + (n-2) + (n-3) + ..... + 1 : 수열의 구하는 공식으로 - O(N^2)

static void sort(int[] arr){
int length = arr.length;

for(int i=0; i<length; i++){
int minIdx = i;

for(int j=i; j<length; j++){
/* 연산 : 비교 */
if(arr[minIdx] > arr[j]){
minIdx = j;
}
}

/* 연산 : 이동 */
int swap = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = swap;
}
}



[삽입정렬]

- 정렬된 것과 정렬되지않은 것을 나눔 : 정렬된 곳에 정렬되지않은 원소를 하나 던져서 위치 정렬

- 시간복잡도

(1) 최악의 경우 : 가장 왼쪽에 위치해야할 , 앞에 정렬된 원소와 모두 비교 한번씩 모두 이동

(2) 비교로 : n번째일 - (n-1), (n-1) + (n-2) + (n-3) + ...

(3) O(N^2)

static void sort(int[] arr){
int length = arr.length;

for(int i=1; i<length; i++){

int std = arr[i];
int idx = i;

for(int j=i-1; j>=0; j--){
if(std < arr[j]){
/* 밀어버리기 */
arr[j+1] = arr[j];
idx = j;
} else {
break;
}
}

arr[idx] = std;
}
}