정렬 알고리즘

     ( 참고 출처 :  https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 )

 : 정렬

 선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 처리되지 않은 데이터중에 맨 앞에 있는 데이터와 바꾸는 것을 반복.
     4 3 2 1
     1 3 2 4
     1 2 3 4
     와 같은 흐름이다.
     
     선택 정렬은 처리되지 않은 데이터 중에서 가장 작은 데이터를 골라내는 연산, 

     맨 앞에 데이터와 바꾸는 연산이 시행이되고
     처리되지 않은 데이터를 골라내는 작업을 반복해서 시행하므로
     시간복잡도는 O(n^2)에 해당한다.


 삽입 정렬 : 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
     선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

     첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하고, 

     이후 데이터들이 첫번째 데이터의 앞으로 들어가는지, 뒤로 들어가는지만 판단한다.
     그리고 세번째 데이터는 첫번째, 두번째 데이터 각각의 앞,뒤의 위치를 판단하게되고 이를 반복한다.

     코딩에 참고하면 좋을 점은,
   

     이 부분에서 앞부분을 정렬해가면서 반복되는 것이기 때문에 

     두번째 반복문을 뒤에서부터 찾아가는 방식으로 연산을 줄일 수 있다.
     최선의 경우 시간복잡도 O(n).

 

 퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법.
     일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나.
     병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘

     가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터 ( Pivot ) 로 설정합니다.

     첫 인덱스의 원소를 피벗 ( pivot )으로 설정하고, 왼쪽에서부터 피벗보다 큰 데이터를 선택하고,
     오른쪽에서부터 피벗보다 작은 데이터를 선택한다.
     그 후 이 데이터의 위치를 서로 변경한다. 

     이때, 왼쪽에서부터 선택한 원소와 오른쪽에서부터 선택한 원소의 위치가 엇갈리는 경우, 
     ( 왼쪽에서부터 선택한 원소가 더 오른쪽에 있는 경우 )
     피벗과 작은 데이터 ( 오른쪽에서부터 선택한 원소 ) 의 위치를 서로 변경한다.

     그렇게되면 피벗의 왼쪽에 있는 데이터는 피벗보다 작고, 우측에 있는 원소는 피벗보다 모두 크다.
     이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할( Divide, Partition )이라 한다.

     이렇게 분할된 왼쪽 그룹과 오른쪽 그룹에 각각 같은 분할작업을 반복한다.

     이를 반복하게되면 이상적일 경우 O(nlog n) 의 시간복잡도를 갖고 정렬이 완료되게 된다.

     n개의 원소를 log n 번의 분할과정을 거치기 때문이다.
  
     다만, 이미 정렬이 완료된 경우와 같이 n개의 원소를 n번의 분할과정을 반복하게 되는 경우와 같이 
     최악의 경우 O(n^2)의 시간복잡도를 가질 수도 있다.
     
     코드를 작성해보았는데, 개념적인건 처음 할때 굉장히 당혹스러웠지만,
     개념적인건 잘 유추해내었다.
     하지만 간결하고 예쁜 코드를 만들지못해 추가했다.


 계수 정렬 : 특정한 조건에 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
     데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능.
     데이터의 개수가 N, 데이터(양수) 중 최댓값이 K 일 때, 최악의 경우에도 수행시간 O(N+K)를 보장합니다.

     계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N+K)이다.
     계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
     예를들어 데이터가 0과 999999 단 2개일 경우를 생각해 볼 수 있겠다.
     
     계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효율적으로 사용할 수 있다.
     ( ex) 성적 )

     구현 방법으로는
     위 조건처럼 데이터의 데이터 ( 양수 ) 의 최대값이 K라 할때,
     K+1의 길이를 갖는 배열을 만들고, 0부터 K까지 원소의 개수를 세어 대응하는 인덱스의 숫자를 증가시키고,
     그렇게 초기화된 배열의 작은 인덱스부터 원소의 갯수만큼 인덱스값을 반환하면 된다.
     말로 간단히 하려니 복잡하니 출처의 영상을 보도록 하자.

     추가로 자바로 표현된 내 코드는

https://github.com/kucnea/CodingTestPractice/blob/master/src/com/algorithm/sortTest/CountSort.java 

     에서 볼 수 있다.