정렬정렬
정렬
정렬정렬
정렬정렬

정렬

다루고 있는 개념
난이도
하
Type
자료
file
정렬 알고리즘정렬 알고리즘 종류선택정렬삽입정렬병합정렬퀵정렬
해당 개념은 영상강의로 이해하시는 것이 빠릅니다. 영상강의를 참고해주세요.

정렬 알고리즘

  • 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다.

정렬 알고리즘 종류

선택정렬

 
  • 선택 정렬은 제자리 비교 정렬이다. 복잡도는 O(n^2)이므로 큰 리스트에는 비효율적이며, 유사한 삽입 정렬보다 성능이 더 떨어지는 것이 일반적이다. 선택 정렬은 단순함이 특징이며 특정한 상황에서는 더 복잡한 알고리즘보다 성능상 우위가 있다.
  • 이 알고리즘은 최솟값을 찾고 값을 최초 위치와 바꾼 다음 리스트의 나머지 부분에 대해 이 과정을 반복한다. 교환 과정은 n개를 넘지 않으므로 교환 비용이 많이 드는 상황에서 유용하다.
 
notion imagenotion image
  • Java 코드
import java.util.Arrays;

public class StackList {
    public static void main(String[] args) {
		    int[] arr = {33, 5, 98, 75, 87, 12, 4, 61, 100};
		    selectionSort(arr);
		         
		    System.out.println(Arrays.toString(arr));
		}
 
 public static void selectionSort(int[] arr) {
      int idxMin, tmp;
     
	    for (int i = 0; i < arr.length - 1; i++) {
	        idxMin = i;
	        for (int j = i + 1; j < arr.length; j++) {
	            if (arr[j] < arr[idxMin]) {
	                idxMin = j;
	            }
	        }
	        tmp = arr[idxMin];
	        arr[idxMin] = arr[i];
	        arr[i] = tmp;
	     }
	 }
}
// 출력
[4, 5, 12, 33, 61, 75, 87, 98, 100]
 
  • Python 코드
def 최솟값_인덱스_리턴_함수 (입력_리스트_둘):
    최솟값인덱스 = 0
    for 증가값 in range(0, len(입력_리스트_둘)):
        if 입력_리스트_둘[증가값] < 입력_리스트_둘[최솟값인덱스]:
            최솟값인덱스 = 증가값
    return 최솟값인덱스

def 선택정렬(입력_리스트_하나):
    최종결과값 = []
    while 입력_리스트_하나:
        최솟값_인덱스_저장 = 최솟값_인덱스_리턴_함수(입력_리스트_하나)
        최솟값 = 입력_리스트_하나.pop(최솟값_인덱스_저장)
        최종결과값.append(최솟값)
    return 최종결과값

주어진리스트 = ['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']

print(선택정렬(주어진리스트))
Out[-]

['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
주어진리스트 = ['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
동물친구들 = {'개구리' : 1 ,
              '거위' : 2,
              '고릴라' : 3,
              '기린' : 4 ,
              '닭' : 5,
              '말' : 6, 
              '북극곰' : 7, 
              '얼룩말' : 8,
              '코끼리' : 9
        }
print(선택정렬(주어진리스트))
Out[-]

['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
 
  • Javascript 코드
function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
      let min_index = i;
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[min_index] > arr[j]) {
          min_index = j;
        }
      }

      let temp = arr[min_index];
      arr[min_index] = arr[i];
      arr[i] = temp;
    }
    return arr;
  }

  const arr = ['개구리', '거위', '말', '북극곰', '얼룩말', '고릴라', '기린', '닭', '코끼리'];
  console.log(selectionSort(arr));
  //['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
 

삽입정렬

  • 삽입 정렬은 작은 리스트와 대부분 정렬된 리스트에 상대적으로 효율적인 단순한 정렬 알고리즘이며 더 복잡한 알고리즘의 일부분으로 사용되기도 한다.
  • 리스트로부터 요소를 하나씩 취한 다음 마치 돈을 지갑에 넣는 방식과 비슷하게 이들을 올바른 위치에, 새로 정렬된 리스트에 삽입함으로써 동작한다. 배열의 경우 새 리스트와 남아있는 요소들은 배열 공간을 공유할 수 있으나 삽입의 경우 잇따르는 모든 요소를 하나씩 이동해야 하므로 비용이 많이 든다. 셸소트는 큰 리스트에 더 효율적인 삽입 정렬의 변종이다.
 
notion imagenotion image
  • Java 코드
public static void main(String[] args) {
   int[] arr = {33, 5, 98, 75, 87, 12, 4, 61, 100};
   insertionSort(arr);

	 System.out.println(Arrays.toString(arr));
	 // 출력 : [4, 5, 12, 33, 61, 75, 87, 98, 100]
}

public static void insertionSort(int[] arr){
     for(int idx = 1; idx < arr.length; idx++) {
         int tmp = arr[idx];
         int aux = idx - 1;

         while(aux >= 0 && arr[aux] > tmp) {
              arr[aux + 1] = arr[aux];
              aux--;
         }

         arr[aux + 1] = tmp;
      }
}
 
  • Python 코드
def 결과값에서_삽입값이들어갈_인덱스 (결과값, 삽입값):
    for 증가값 in range(0, len(결과값)):
        if 삽입값 < 결과값[증가값]:
            return 증가값
    return len(결과값)
def 삽입정렬(입력_리스트_하나):
    결과값 = []
    while 입력_리스트_하나:
        삽입값 = 입력_리스트_하나.pop(0)
        삽입값_인덱스 = 결과값에서_삽입값이들어갈_인덱스(결과값, 삽입값)
        결과값.insert(삽입값_인덱스, 삽입값)
    return 결과값

주어진리스트 = ['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']

print(삽입정렬(주어진리스트))
Out[-]

['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
주어진리스트 = ['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
동물친구들 = {'개구리' : 1 ,
              '거위' : 2,
              '고릴라' : 3,
              '기린' : 4 ,
              '닭' : 5,
              '말' : 6, 
              '북극곰' : 7, 
              '얼룩말' : 8,
              '코끼리' : 9
        }
정렬된리스트 = 삽입정렬(주어진리스트)
for 정렬값 in 정렬된리스트:
    for 동물친구 in 동물친구들:
        if 정렬값 == 동물친구:
            print(동물친구)
Out[-]

['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
 
  • Javascript 코드
function insertIndex(sorted_arr, value) {
    for(let i in sorted_arr){
      if(value < sorted_arr[i]){
        return i;
      }
    }
    return sorted_arr.length;
}

function insertSort(arr) {
   let sorted_arr = [];

   while (arr.length != 0){
     let value = arr.shift();
     let index = insertIndex(sorted_arr, value);
     sorted_arr.splice(index, 0, value);
   }
   return sorted_arr;
}
const arr = ['개구리', '거위', '말', '북극곰', '얼룩말', '고릴라', '기린', '닭', '코끼리'];
console.log(insertSort(arr));
//['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
 

병합정렬

  • 합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다.
  1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
  1. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  1. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  1. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시 배열에 저장된다.
  1. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
notion imagenotion image
  • Java 코드
public static void main(String[] args) {
     int[] arr = {33, 5, 98, 75, 87, 12, 4, 61, 100};
     mergeSort(arr, 0, arr.length - 1);
        
     System.out.println(Arrays.toString(arr));
     // 출력 : [4, 5, 12, 33, 61, 75, 87, 98, 100]
}

public static void mergeSort(int[] arr, int left, int right) {
     if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
     }
}

public static void merge(int[] arr, int left, int mid, int right) {
     int i = left, j = mid + 1, k = left;
     int[] tmp = new int[arr.length];

     while (i <= mid && j <= right) {
         if (arr[i] <= arr[j]) {
             tmp[k++] = arr[i++];
         }
         else {
             tmp[k++] = arr[j++];
         }
     }
        
     while (i <= mid) {
	        tmp[k++] = arr[i++];
     }

     while (j <= right) {
	        tmp[k++] = arr[j++];
     }

     for (int idx = left; idx <= right; idx++) {
          arr[idx] = tmp[idx];
     }
}
 
  • Python 코드
def 병합정렬(입력리스트):
    입력리스트길이 = len(입력리스트)
    if 입력리스트길이 <= 1:
        return 입력리스트

    중간값 = 입력리스트길이 // 2
    그룹_하나 = 병합정렬(입력리스트[:중간값])
    그룹_둘 = 병합정렬(입력리스트[중간값:])
    결과값 = [ ]
    
    while 그룹_하나 and 그룹_둘:
        if 그룹_하나[0] < 그룹_둘[0]:
            결과값.append(그룹_하나.pop(0))
        else:
            결과값.append(그룹_둘.pop(0))
    while 그룹_하나:
        결과값.append(그룹_하나.pop(0))
    while 그룹_둘:
        결과값.append(그룹_둘.pop(0))
    return 결과값
주어진리스트 = ['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']

print(병합정렬(주어진리스트))
Out[-]

['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
 
  • Javascript 코드
function mergeSort(arr){
  if (arr.length <= 1){
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
  let result = [];

  while (left.length && right.length){
    if (left[0] < right[0]){
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }

  return result;
}

const arr = ['개구리', '거위', '말', '북극곰', '얼룩말', '고릴라', '기린', '닭', '코끼리'];
console.log(mergeSort(arr));
//['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
 

퀵정렬

  • 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.
  1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
  1. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
  1. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
 
notion imagenotion image
  • Java 코드
public static void main(String[] args) {
     int[] arr = {33, 5, 98, 75, 87, 12, 4, 61, 100};
     quickSort(arr, 0, arr.length - 1);
        
     System.out.println(Arrays.toString(arr));
     // 출력 : [4, 5, 12, 33, 61, 75, 87, 98, 100]
}

public static void quickSort(int[] arr, int p, int r) {
	   if(p < r) {
        int q = partition(arr, p, r);
        quickSort(arr, p, q - 1);
        quickSort(arr, q + 1, r);
     }
}

public static int partition(int[] arr, int p, int r) {
     int i = p, j = r;
     int pivot = arr[p];

     while(i < j) {
         while(pivot < arr[j]) {
             j--;
         }

         while(i < j && pivot >= arr[i]){
             i++;
         }

         int tmp = arr[i];
         arr[i] = arr[j];
         arr[j] = tmp;
	  }
    arr[p] = arr[i];
    arr[i] = pivot;

    return i;
}
 
  • Python 코드
def 퀵정렬(입력리스트):
    입력리스트길이 = len(입력리스트)
    if 입력리스트길이 <= 1:
        return 입력리스트
    기준값 = 입력리스트[-1]
    그룹_하나 = []
    그룹_둘 = []
    for 증가값 in range(0 , 입력리스트길이-1):
        if 입력리스트[증가값] < 기준값:
            그룹_하나.append(입력리스트[증가값])
        else:
            그룹_둘.append(입력리스트[증가값])
    return 퀵정렬(그룹_하나) + [기준값] + 퀵정렬(그룹_둘)

주어진리스트 = ['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']

print(퀵정렬(주어진리스트))
Out[-]

['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']
 
  • JavaScript 코드
function quickSort(arr){
    if (arr.length <= 1){
      return arr;
    }

    const pivot = arr[0]; //기준점
    const left = [];
    const right = [];

    for (let i=1; i<arr.length; i++){
      if(arr[i] < pivot){
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}

const arr = ['개구리', '거위', '말', '북극곰', '얼룩말', '고릴라', '기린', '닭', '코끼리'];
console.log(quickSort(arr));
//['개구리', '거위', '고릴라', '기린', '닭', '말', '북극곰', '얼룩말', '코끼리']