[알고리즘] 기본 정렬 알고리즘 (Sorting Algorithm)

정렬 알고리즘 개요

Name	Best	Worst (Big-O)	Stable	Memory
선택정렬	n²	n²	False	1
버블정렬	n	n²	True	1
삽입정렬	n	n²	True	1
합병정렬	nlogn	nlogn	True	n
힙 정렬		nlogn		1
퀵 정렬	nlogn	nlogn	False	1

1. 선택정렬(Selection Sort)

① 개요 

• 한번 순회를 하면서 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.
• 최소 선택 정렬(Min-Selection Sort) : 오름차순으로 정렬
• 최대 선택 정렬(Max-Selection Sort) : 내림차순으로 정렬

② 기본 로직

1.  정렬 되지 않은 인덱스의 맨 앞부터, 그 이후의 배열값 중 가장 작은 값을 찾아간다.
2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
3. 위 과정을 반복한다.

③ 복잡도

1. 시간복잡도 : O( n²)  => n-1, n-2, .... , 1개씩 비교를 반복하므로 대략 n(n-1) / 2번 수행된다.
2. 공간복잡도 : O( n ) 

④ 코드 

	public void selectionSort(int[] ary) {
	int size = ary.length;
	for(int i = 0; i < size - 1; i++) {
	int min_idx = i;
	for(int j = i + 1; j < size; j++) {
	if(ary[min_idx] > ary[j]) {
	min_idx = j;
	}
	}
	if (min_idx == i) {
	continue;
	}
	int temp = ary[min_idx];
	ary[min_idx] = ary[i];
	ary[i] = temp;
	}
	}

view raw SelectionSort.java hosted with ❤ by GitHub

2. 버블정렬(Bubble Sort)

① 개요 

• 바로 가까이에 있는 두 숫자끼리 비교를 해서 더 작은 숫자를 앞으로 보내주는 것을 반복
• 비교할 때마다 큰 값이 뒤로 이동하여, 1바퀴 돌 때 가장 큰 값이 맨 뒤에 저장된다.
• (전체 배열의 크기 - 현재까지 순환한 바퀴 수) 만큼만 반복
• 컴퓨터 내부적인 연산이 가장 비효율적으로 일어나게 되어 실제 수행시간이 가장 안 좋은 알고리즘

② 기본 로직

1. 두 번째 인덱스부터 시작한다. 현재 인덱스 값과 바로 이전 인덱스 값을 비교한다.
2. 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
3. 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.
4. (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

③ 복잡도

1. 시간복잡도 : O( n²) 
2. 공간복잡도 : O( n ) 

④ 코드 

	public void bubbleSort(int[] ary) {
	int size = ary.length;
	for(int i = 0; i <size - 1; i++) {
	for(int j = 1; j < size - i; j++) {
	if(ary[j-1] > ary[j]) {
	int temp = ary[j];
	ary[j] = ary[j-1];
	ary[j-1] = temp;
	}
	}
	}
	}

view raw BubbleSort.java hosted with ❤ by GitHub

3. 삽입정렬(Insertion Sort)

① 개요 

• 현재 Index 위치에서 현재 Index보다 작은쪽을 비교하여 자신이 들어갈 위치를 찾아 삽입하는 알고리즘
• 기본적으로 정렬 되어 있다는 상황에서 가장 빠른 알고리즘 ▶O( n )

② 기본 로직

1. 두 번째 Index부터 시작한다. 현재 Index 값은 별도의 변수(currentValue)에 저장하고, 비교 Index(Position)를 현재 Index로 잡는다.
2. 별도로 저장해 둔 삽입을 위한 변수(currentValue)와 비교 Index-1 의 배열 값을 비교한다.
3. 삽입 변수의 값이 더 작으면 현재 Index-1의 값을 저장해주고, 비교 Index(Position)를 -1하여 비교를 반복한다.
4. 만약 삽입 변수가 더 크면 while문을 빠져나와 비교 Index(Position)에 삽입 변수를 저장한다.

③ 복잡도

1. 시간복잡도 : O( n²) , 참고로 Best일 때  : O( n ) : while문 조건에서 O(1)이기 때문에
2. 공간복잡도 : O( n ) 

④ 코드 

	public void insertionSort(int[] ary) {
	int size = ary.length;
	for(int i = 1; i <size; i++) {
	int currentValue = ary[i];
	int position = i;
	while(position > 0 && ary[position-1] > currentValue) {
	ary[position] = ary[position-1];
	position--;
	}
	ary[position] = currentValue;
	}
	}

view raw InsertionSort.java hosted with ❤ by GitHub

참고

1. https://blog.naver.com/ndb796/221226800661
2. https://jongmin92.github.io/2017/11/06/Algorithm/Concept/basic-sort/
3. http://hsp1116.tistory.com/33
4. https://medium.com/@joongwon/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88-805391cb088e