Sorting 알고리즘?

• 사전 처럼 A부터 Z까지 기준으로 정렬
• 큰수에서 작은 수를 기준으로 정렬
• 원하는 기준에 맞춰서 배열의 데이터들을 정리하는 알고리즘

  왜 필요함?
  각 정렬 알고리즘의 원리와 차이점을 비교하며 어떤 기준으로 선택해야 하는지 결정해야 한다. Sorting은 많은 개발자의 관심을 갖는 개념이다. 성능에서 많은 차이가 나고 많이 사용한다.

Shorting Algorithm 3가지

1. Bubble Sort / 버블정렬

• 자주 사용하는 알고리즘은 아니다. (성능이 안좋다. 하지만 Sorting 알고리즘을 이해하기 쉽다.)
• 배열의 2개의 아이템을 선택하고, 두개의 크기를 비교해서 위치를 바꿔가면서 정렬하는 알고리즘이다.
• 버블정렬의 시간복잡도는 O(n^2)
  
  

2. Selection Sort / 선택정렬

• 전체 아이템 중에서 가장 작은 아이템의 위치를 찾아 그 위치를 변수에 저장한다. 그리고 맨 첫번째 아이템과 위치를 바꾼다.
• 정렬된 첫번째 아이템은 제외 후, 다시 과정을 반복한다.
• 선택정렬의 시간복잡도? O(n^2)
  버블정렬과 유사하게 스왑도 있고, 비교도 있다. 정렬되지 않은 배열에서 가장 작은숫자를 찾으므로 이건 N-1 비교를 하는 것이다. 이건 버블정렬과 같다. 버블정렬과 다르게 N번의 스왑을 하지는 않는다. 매번 싸이클마다 1번의 스왑만 진행된다.
  
  

3. Insertion Sort / 삽입정렬

• 삽입정렬은 배열의 1번 index 아이템을 선택하고 왼쪽에있는 아이템과 비교하여 정렬을 한다.
• 삽입정렬은 선택정렬보다 빠르다.
• 왜냐면 삽입 정렬은 필요한 아이템만 스캔한다. 선택정렬은 전체 모든 아이템을 스캔한다.
• 시간복잡도는 O(n^2)
  
  

Big O 쓸모없자나?

3가지 종류의 알고리즘을 정리해봤지만 성능은 각각 다르지만 모두 같은 시간복잡도를 가지고있다.

이 경우 최악의 시나리오를 보지말고, 평균 시나리오를 살펴봐야한다.

최악/최고의 케이스는 자주 발생하지 않고 대부분 평균 수준에 속해있다.

그걸 감안하고 해당 알고리즘을 보면, 삽입정렬 선택정렬 둘 다 평균적으로, 최악의 경우 이차 시간복잡도를 가지고있다.

하지만 최고의 케이스 경우 O(N) 선형 시간복잡도를 가지게된다.

그렇기에 우리는 알고리즘의 디테일을 알아야하고 문제 해결에 사용해야한다.

삽입, 선택 정렬은 작은 DB기준으로는 훌륭한 알고리즘이다.

물론 데이터가 커질수록 좀 느려지겠지만. 그때는 다른 방법을 찾아봐야한다. 다음시간에