23/12/12 TIL __ 정렬 알고리즘

  

 

 

오늘은 정렬에 대해 적어보려 한다.

대표적인 정렬 알고리즘 5개가 있다. 

버블정렬, 선택정렬, 삽입정렬, 병합정렬, 퀵정렬

 

 

 

1. 버블정렬

• 0번째 부터 순차적으로 1:1  비교를 해서 계속 정렬을 해나간다.
• 뒤에서부터 정렬이 된다. 

 

 

 

 

 

2. 선택정렬

• 현재 위치에 맞는 자료를 찾아 선택해 위치를 교환한다. 
• 가장 작은값을 찾아 정렬하며, 앞에서부터 정렬을 한다.
• 0~ n번  인덱스중 가장 작은값을 찾아 0번째와 교체
• 1 ~ n번 인덱스중 가장 작은값을 찾아 1번째와 교체
• 반복한다.

 

 

 

 

3. 삽입정렬

 

• 앞에서부터 차례로 비교하며 정렬한다.
• 0번 인덱스는 건너뛴다.
• 0~1번 인덱스 중 1번 인덱스 값이 들어가야할 위치를 찾아서 넣는다
• 0~2번 인덱스 중 2번 인덱스 값이 들어가야할 위치를 찾아서 넣는다

 

 

4. 병합정렬

 

• 자료를 잘게 쪼개서 비교 후 병합을 한다. 
• [1,2,3,4] 라는 자료라면, length가 1이 될때까지 쪼갠다.
• [1,2], [3,4]
• [1], [2], [3], [4]
• 1과 2중 1이 더 작으니 이렇게 병합 [1,2]
• 3과 4중 3이 더 작으니 이렇게 병합 [3,4]
• [1,2]의 0번 인덱스와, [3,4]의 0번 인덱스를 비교해 정렬
• [1], [2], [3,4]에서 또 [2]와 [3,4]의 0번 인덱스를 비교해 정렬
• 보통 재귀함수로 구현됨. (같은방식 계속 반복 병합)

 

 

5. 퀵정렬

 

• 병합정렬과 마찬가지로 분할정복을 통한 정렬법
• 입력된 자료들중 하나의 원소를 고르는데 이게 피벗이라고 한다. 
• 이걸 기준으로 리스트를 2개로 나눈다.
• 이걸 기준으로 이 피벗보다 작은 원소는 모두 피벗 왼족
• 크면 오른쪽으로 옮긴다.

 

아직 실제 코드구현을 어떻게 해야할지는 좀더 공부를 하며 익혀야 겠다.

 

 

 

참고한 사이트

https://evan-moon.github.io/2018/10/13/sort-algorithm/

정렬 알고리즘 정리 (Bubble, Selection, Insertion, Merge, Quick)