코공해적단 동료들과 함께 정렬 알고리즘에 대해 공부했다.
처음엔 쉬웠는데 합병부터 힘들었다.
퀵은 아직도 어려워서 그냥 코드보고 이해하는 중.
경고
코딩 공부 아직 54일차에 쓰는 찌끄레기 찐따가 공부하고 작성한 것이라 정보가 유익하지 않거나, 부족하거나, 잘못될 수 있음을 알림.
본인은 최대한 간단하게 적는 것을 좋아해서 생략된 부분이 많음.
선택 정렬(Selection Sort)
현재 위치에 들어갈 값을 찾아 정렬하는 배열 (i와 배열 전부)
제자리 정렬 알고리즘의 하나.
(제자리 정렬이란? 주어진 공간 외에 추가적인 공간을 사용하지 않는 정렬)
선택 정렬 알고리즘은 최소 선택 정렬(오름차순)과 최대 선택 정렬(내림차순)으로 나뉜다.
그림으로 보는 선택정렬 알고리즘
이미지 출처 - https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC
특징
시간 복잡도 O(n2)
제자리 정렬이기 때문에 메모리가 절약된다.
알고리즘이 단순하고 직관적이다.
시간 복잡도가 오래 걸려 성능이 떨어진다.
Pseudo-code
Selection Sort 오름차순 수도코드
1. 배열을 반복하여 가장 작은 값의 위치와 값을 찾자.
2. 그 값을 배열의 제일 첫 번쨰 (arr[0])과 바꿔준다.
3. 맨 앞(바꿔준 값)을 제외하고 다시 배열에서 가장 작은 값을 찾는다.
4. 그 값을 2번(순서)의 다음 값으로 바꿔준다. (arr[1])
5. 1~4를 배열의 길이만큼 반복한다.javascript code
삽입 정렬(Insertion Sort)
현재 위치에서 그 전의 배열들을 비교하며(i와 i-1) 현재 위치가 들어갈 곳을 찾아 넣는 정렬 알고리즘.
배열의 두 번째 위치부터 시작한다.
EX) 두 번쨰 값은 첫 번째 값과 비교, 세 번째 값은 첫 번쨰와 두 번째 값을 비교.
특징
평균 시간 복잡도는 O(n2).
하지만 배열이 이미 정렬되어 있으면 1번만 순회를 하기에 O(n)이 된다.
대부분의 값들이 정렬되어 있을 경우 효율적이다.
제자리 정렬이기 때문에 메모리가 절약된다.
Pseudo-code
insertion Sort 오름차순 수도코드
1. 반복문을 통해 배열의 두 번째 값을 시작으로 하자.
2. 두 번째 값과 첫 번째 값을 비교하여, 두 번째 값이 더 작으면 서로 바꿔주자.
3. 세 번째 값을 할 때는 두 번째 값과 비교 후 교체,
다시 두 번째 값을 첫 번째 값과 비교 후 교체.
4. 2~3을 반복.. 네 번째는 세 번째와 비교.. 다시 세 번째와 두 번째를 비교..
5. 배열의 길이 만큼 반복시켜 주자.javascript code
버블 정렬(Bubble Sort)
i와 i+1를 계속 비교하며 값을 바꿔 정렬하는 알고리즘.
1번 순회할 때마다 가장 큰 값이 배열의 마지막에 가게 된다.
n번 반복할 때마다 (배열의 길이 - n)을 해주면 바꿔줬던 값을들 제외하고 비교 가능.
내가 그린 버블 정렬
특징
시간 복잡도는 O(n2).
제자리 정렬이기 때문에 메모리가 절약된다.
이미 정렬된 데이터라면 O(n)으로 줄일 수 있다.
Pseudo-code
bubble Sort 오름차순 수도코드
1. 반북문을 통해 j와 j+1을 비교해주자.
2. 비교해서 큰 값을 j+1로 바꿔주자.
3. 배열의 전체 길이 만큼 1~2를 반복하자
4. n번 째 반복할 때는 j의 크기 제한을 (전체길이-n)로 해주자.
5. 값이 바뀔 때 마다 count를 하여, 이미 정렬된 배열이라면 반복을 1번만 해주자.javascript code
합병 정렬 (Merge Sort)
분할 정복 알고리즘 종류의 하나.
분할 정복은 큰 문제를 반으로 쪼개 해결해 나가는 방식을 말함.
병합 정렬은 최선의 경우에도, 최악의 경우에도 O(nlog₂n)의 시간이 소요되기 때문에 데이터 분포에 영향을 덜 받는다. 항상 동일한 시간이 소요되므로 어떤 경우에도 좋은 성능을 보장받을 수 있다.
그림으로 보는 합병
이미지 출처 - https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
Pseudo-code
merge Sort 오름차순 수도코드
1. 주어진 배열을 가운데를 기준으로 반으로 나누는 코드를 짠다.
2. 배열을 더 이상 나눌 수 없을 때까지 나눈다.
3. 반으로 나눈 배열을 합쳐주는 배열의 인자로 넣는다.
4. 두 값을 비교하여 작은 값을 빈 배열에 넣고 합친다.javascript code
퀵 정렬 (Quick Sort)
분할 정복 알고리즘 종류의 하나.
퀵 정렬은 기준점(pivot)을 정한다. 그 후, pivot보다 작으면 기준의 왼쪽, 크면 오른쪽에 넣는다.
pivot 왼쪽에 놓여진 기준 원소보다 작은 배열에서 위와 같은 방법으로 다시 pivot을 설정하고 배열을 pivot을 기준으로 나눈다.
이 방법을 반복하면 결국 기본 단계인 원소가 하나만 있는 배열이 남는다.
구현 방법은 기준점이나, 왼쪽, 오른쪽으로 나누는 방법에 따라 다양하다.
Pseudo-code
quick Sort 오름차순 수도코드
1. 먼저 기준점인 pivot을 정한다.
2. pivot보다 작으면 left에 넣고, 크면 right에 넣는다.
3. 비교 도중 i와 pivot을 비교하게 되면 따로 저장한다.
4. 합쳐주자 !javascript code
코드 참고
https://im-developer.tistory.com/135
퀵은 나에게 아직 무리였따.
코콩해적단 파이팅
bubble sort ~