정렬 알고리즘

알고리즘 공부하면서 정리도 하기로 했음.

개인공부용이라 정리가 제 맘대로일 수 있습니다.

 

Selection Sort 선택정렬

제일 낮은 거 선택해서 맨 앞으로 보내는 가장 직관적인 그 알고리즘!

간단한거라면 굳이어려운걸 하기 보다 걍 파악하기 쉽게 이 알고리즘을 쓰는 것도 좋다만,

데이터가 크면 클수록 시간복잡도가 높아지기에 굳이 할 필요 없는 그 알고리즘

초보자용이랄까?

풋내기용이라니 마치 나같군

1부터 10을 정렬하려면 55번의 비교연산이 필요함.  근데 만개의 데이터라면 일억번해야됨.

근데 심지어 더 줄어들지도 않음. 애당초 1,2,3,4,5,6,7,8,9,10 으로 되어있어도 55번 비교함.

시간복잡도 = O(n^2)

 

Bubble Sort 버블정렬

옆에 있는 녀석과 비교해서 더 작은값을 앞으로 보낸다.

와 이해하기 정말 쉽다~ 군대나 학교에서 운동장에 쭈욱 서있을 때 앞 뒷사람만 키 비교해서 정렬을 자연스럽게 할 수 있네?

너무 좋다~ 코드도 너무 쉽게 구현될 것 같아. 그러니까 빠르겠지?

이지만 시간복잡도로 생각하면 그게 아님.

결국 10 + 9 +.. 의 횟수를 해야하는데 

실제론 선택정렬과 비교해서 자리를 바꾸는 걸 계속 하기 때문에 연산량은 선택정렬보다도 많다구....

시간복잡도 = O(N^2)

 

Insertion Sort 삽입정렬

 

숫자를 적절한 위치에 삽입한다!

위에꺼 두 개랑 다르게 필요할 때만 위치를 바꾼다.

앞에서부터 정렬을 해나가는데

정렬이 되어있는 상태니까 현재의 원소가 멈출 포인트까지만 확인할 수 있음.

그런데 최악의 경우를 가정하면 위에껏들과 시간복잡도가 다르진 않지만

실제로는 위의 두 정렬(선택정렬, 버블정렬)보단 훨 나음

삽입정렬이 유용할 때는 언제냐면 정렬이 많이 되어있는 데이터의 경우에 상당히 빠르게 할 수 있다~

시간복잡도 = O(N^2)

 

Quick Sort 퀵정렬

 

매우매우 중요한 정렬. 노말한 경우에는 이걸 쓰는 게 좋다.

근데 처음에 이해는 잘 안되었음.

이렇게 함

1. 피벗을 설정한다. 첫 위치에 있는 값으로 설정.

2. 데이터의 시작지점부터 피벗보다 큰 녀석을 찾는다

3. 데이터의 끝지점부터 피벗보다 작은 녀석을 찾는다.

4. 2와 3을 잘 찾았으면 둘의 위치를 바꿔줌.

5. 2가 3보다 더 큰 위치에 있다면, 둘이 엇갈린거임. 이 때는 3번에서 찾은 것과 키값을 바꿔줌

6. 이제 원래 키값이었던 아이가 들어간 위치에 그 녀석을 고정시키고 걔를 기준으로 왼쪽 그룹과 오른쪽 그룹을 1~5를 반복한다.

 

귀찮아서 대충 적었는데 암튼

일반적으로 아주 빠른 정렬이지만

이미 정렬이 잘 되어있는 경우에는 삽입 정렬보다 느리다.

맹신하면 안된다 이말이다

 

시간복잡도 = O(nN*logN)

 

--
이렇게 4개의 정렬이 기초 정렬 4대장임.

다들 쉬운 알고리즘임. 

 

업데이트 예정...