[Algorithm] 정렬

 

 

Sorting 정렬

 

 

1. Selection Sort 선택정렬

가장 간단하지만 효율성이 떨어지는 정렬 알고리즘

기본 아이디어는 매 순환(linear search)에서 가장 작은/큰 요소를 찾아서 위치를 이동하여 정렬함

 

리스트에서 최소값 찾음

↓

그 값을 첫번째 값과 교환

↓

남은 리스트 중 가장 작은 값을 두번째 값과 교환

↓

이 과정을 전체 리스트가 정렬될 때 까지 반복 

n * n-1

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

 

 

 

2. Insertion Sort 삽입정렬

리스트의 두번째 요소부터 시작하여 현재 키를 그 이전의 모든 요소와 비교함

↓

키가 이전 요소보다 작으면 이전 요소를 한 위치 오른쪽으로 이동시킴

↓

키가 이전 요소보다 큰 위치를 찾을 때 까지 혹은 모든 이전 요소를 확인 할 때 까지 반복

↓

원하는 위치에 키 값을 삽입

↓

해당 과정을 모든 요소에 대해 반복하여 정렬

 

 

 

 

 

 

3. Bubble Sort 버블정렬

이웃한 두 요소를 비교하여 큰(작은) 값을 뒤로 거품처럼 떠오르게 하는 방식

 

1. 리스트의 처음부터 시작해서 이웃한 두 요소를 비교

2. 만약 첫번째 요소가 두번째 요소보다 크다면 두 요소의 위치를 바꿈

3. 위 과정ㅇ을 리스트의 마지막까지 반복

=> 가장 큰 값이 리스트의 마지막 위치로 이동함

4. 위 과정을 전체 리스트에 대해 반복하여 전체 리스트를 정렬함

시간복잡도 O(n^2)

이미 정렬한건 다시 안봐도 돼서 -j 해줌

안에 i 반복문 : 위에 3번까지

밖에 j 반복문 : 4번

 

 

 

 

 

 

4. Merge Sort 병합정렬

분할 정복(Divide and Conquer) 방식을 사용하는 알고리즘

리스트를 계속 반으로 나누어 각 부분을 개별적으로 정렬한 뒤 합치면서 리스트를 정렬하는 방식

 

 

1. 주어진 리스트를 절반으로 나눔. 각 부분의 리스트의 크기가 1이 될때까지 반복

2. 각 부분을 병합하면서 정렬함. 두 부분의 첫번째 요소부터 비교하여 결과 리스트에 추가함

3. 한 부분의 리스트의 모든 요소가 결과에 추가되면 남은 요소를 전부 추가함

4. 위 과정을 전체 부분에 대해 반복하여 리스트를 정렬함

시간 복잡도 : O(n log n)

>> 대용량 데이터에서 마니 사용됨

이거

 

 

 

5. Quick Sort 퀵정렬

퀵 정렬은 리스트를 임의의 피벗 값으로 분할하고

피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킴

>> 랜덤으로 하나 뽑아와서 걔 기준으로 정렬시키는거

>> 보통은 중간꺼로 많이 함

 

1. 리스트에 하나의 요소( 피벗 )를 선택함

2. 피벗을 기준으로 리스트를 두 부분으로 분할, 피벗보다 작은부분과 피벗보다 큰 부분

3. 각 부분 리스트의위 과정을 재귀적으로 반복해서 리스트를 정열함

 

평균시간복잡도: O(n log n)

최악의 경우: O(n^2)

 

실제 서비스에서 일반적으로 좋은 성능을 보여주며(최악의경우가잘안나옴)

인-플레이스 알고리즘으로 추가메모리를 거의 사용하지 않아 많이 사용됨