[알고리즘] 기본 정렬 알고리즘 (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 ) 

④ 코드 

2. 버블정렬(Bubble Sort)

① 개요 

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

② 기본 로직

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

③ 복잡도

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

④ 코드 

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 ) 

④ 코드 

참고

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