20181112

정렬 알고리즘

버블 정렬

• 붙어있는 원소끼리 비교.
• 가장 뒷 쪽부터 정렬된다.
• 매우 비효율적이나 구현이 쉽다.
• n-1, n-2, … , 1

삽입 정렬

• 손 안에 있는 카드를 정렬하는 것과 유사하다.
• 내 앞의 인덱스의 값을 확인하고, 내가 더 작으면 arr[인덱스+1] = arr[인덱스] (큰 값을 한 칸 오른쪽으로 민다.)
• 내가 내 앞의 인덱스의 값보다 더 클 경우 확인한 인덱스 + 1에 내가 들어간다.
  • 내 앞의 인덱스가 더 이상 없을 경우 인덱스 0에 내가 들어간다.
• 베스트의 경우(정렬되어 있는 경우) 시간복잡도 n.
• 1, 2, 3, … , n-1

선택 정렬

• 주어진 리스트 중 최소 값을 찾아 맨 앞의 원소와 교체.
• 가장 앞 쪽부터 정렬된다.
• 비교횟수는 많으나, 교체 횟수가 적은 것이 장점.
• 역순일 때 가장 빠르다.