[Java] 알고리즘 Day6

정렬

1. 선택정렬

• 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬
• 연산 횟수는 N+(N-1)+(N-2)+ … +2 = (N² + N)/2 번
• 시간 복잡도는 O(N²)이므로 알고리즘 문제 풀이에 사용하기에는 느림
  

  

2. 삽입정렬

• 첫 번째 데이터가 정렬되어 있다고 가정하고 두 번째 데이터부터 탐색하여 첫번째 데이터보다 작으면 앞, 크면 뒤에 삽입한다.
• 삽입 정렬은 데이터가 거의 정렬 되어 있을 때 훨씬 효율적
• 삽입 정렬의 시간 복잡도는 시간 복잡도는 O(N²)지만 데이터가 거의 정렬되었을 때는 빠르게 동작하여 최선의 경우 O(N)의 시간 복잡도를 가짐
  

  

3. 퀵정렬

• 피벗을 선정하여 피벗보다 작은 값을 왼쪽으로, 큰 값을 오른쪽으로 분할하여 정렬
• 두 부분으로 나눠진 부분에서 다시 피벗을 선정하여 정렬
• 퀵 정렬의 평균 시간 복잡도는 O(NlogN)