정렬 알고리즘이란?

#알고리즘 #코딩 #노마드 코더

본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다.

---

정렬 알고리즘이란?

 Sorting : 뜻대로 정렬하는 것

 그 중 배열 정렬 중에서 이해하기 쉬운 3가지 정렬을 살펴보도록 하자.

 

1. Bubble Sort(버블 정렬)

시간 복잡도 : O(n^2) ...................................................( 스포하자면 이번에 공부할 3가지 정렬 모두 시간 복잡도는 같다 )

버블 정렬은 잘 사용되지 않음 좋은 알고리즘은 아님. 그러나 이해하기 쉬운 알고리즘이다.

원리는 간단하다. 배열에서 두개를 선택하여 선택된 왼쪽이 오른쪽보다 크면 swap을 하여 정렬하는 방식

 

버블 정렬 예시 : java

for(int i=0;i<arr.length-1;i++) {
  for(int j=0;j<arr.length-1-i;j++) {
    if(arr[j]>arr[j+1]) {
      int temp=arr[j];
      arr[j]=arr[j+1];
      arr[j+1]=temp;
    }
  }
}

 

2. Selection Sort(선택 정렬)

시간 복잡도 : O(n^2)

선택 정렬은 가장 작은 숫자를 찾고 맨 앞에 두고 첫번째 인덱스를 제외한 가장 작은 숫자찾고 앞에 두고를 N-1번 반복한다.

장점은 버블정렬과 다르게 한번의 swap이면 다음번으로 넘어간다. 따라서 버블 정렬보다 두배나 빠르다. 하지만 역시 같은 시간 복잡도를 가진다.(복잡도는 메세지 기준이므로)

 

선택 정렬 예시 : java

int[] a = {}; // 정렬할 배열
int b;
for(int i = 0 ; i <  a.length -1 ; i ++) {
  for(int j = i+1 ; j < a.length ; j ++) {
    if(a[i] > a[j]) {
      b = a[j];
      a[j] = a[i];
      a[i] = b;
    }
  }
}

 

3. Insertion(삽입 정렬)

시간 복잡도 : O(n^2)

삽입 정렬은 차례로 가면서 왼쪽보다 작으면 이동하여 마치 맨 뒤에서 부터 차곡차곡 큰 수대로 쌓인다고 생각하면 된다. 이 역시 선택 정렬보다 빠르다.

 

삽입 정렬 예시 : java

int[] a = {}; // 정렬할 배열
int b,j;
  for(int i = 1 ; i < a.length ; i ++) {
    b = a[i];
    for(j = i-1 ; j >= 0 && a[j] > b; j --) {
    	a[j+1] = a[j];
    }
  a[j+1] = b;
}

 

알고리즘은 항상 평균 시나리오를 살펴봐야한다. 그 이유는 당연히 최악과 최고의 시나리오는 자주 발생하지 않기 때문에 평균 시나리오를 기준으로 삼아야 한다.

따라서 삽입, 선택정렬 모두 이차(N^2) 시간복잡도를 가지고 있지만 삽입 정렬의 경우 최고의 시나리오에서 시간복잡도는 O(n)이 되는 것과 같이 상황에 맞춰 알고리즘을 사용하면 된다. 추가로 이 정렬은 작은 DB기준 최고의 알고리즘이 될 것이다.

반면에 큰 용량을 가졌을때 유용한 정렬은 Quick Sort , Merge Sort 있다.

 

오늘 성장에 도움을 주신 개발자분들 

참고문헌 : 노마드 코더 - https://www.youtube.com/watch?v=Bor_CRWEIXo