정렬(Sort)

● 선택정렬(Selection Sort) - 앞에서부터 정렬

 - n개의 숫자가 있을때 n-1회전이 진행

 - i가 진행되면서 가장 작은 수를 기억

 - i -> n까지 진행되면서 기억해놓은 가장 작은수를 가장 왼쪽의 수와 교환

 - 가장 작은수가 가장 왼쪽으로 이동하게됨

 - O(n^2)

 

● 버블정렬(Bubble Sort) - 뒤에서부터 정렬

 - n개의 숫자가 있을때 n-1회전이 진행

 -  i -> n-1까지 진행되면서 i와 i+1을 비교해서 i>i+1이면 교환하고 i<i+1이면 교환X (오름차순 정렬시)

 - 가장 큰수가 가장 오른쪽으로 이동하게됨

 - O(n^2)

 

● 삽입정렬(Insertion Sort) - 앞에서부터 정렬

 - n개의 숫자가 있을때 n번 진행

 - 앞에서부터 하나씩 자기 위치를 찾아 삽입하면서 정렬해 나감

    -> 지나온 부분 : 정렬된 부분/ 지나지 않은부분 : 아직 정렬되지 않은 부분

 - 갯수가 많을 수록 효율이 떨어짐 (많은 이동을 이르킴)

 - O(n^2)

 

● 병합정렬(Merge Sort) 

 - 중간을 기준으로 왼쪽 절반 정렬, 오른쪽 절반 정렬 후 병합함

 - 원소가 한개가 될때까지 계속해서 반으로 나눈 후 다시 합쳐가면서 정렬함

 - O(n log n)