정렬 알고리즘 - 단순 선택, 단순 삽입

단순 선택 정렬

• 단순 선택 정렬은 가장 작은 요소부터 선택하여 알맞은 위치에 옮겨 정렬하는 알고리즘이다.
• 서로 떨어진 요소를 교환하기 때문에 안정적이지 않다.

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

 

Python Code

def selectionSort(x):
	length = len(x)
	for i in range(length-1):
	    indexMin = i
		for j in range(i+1, length):
			if x[indexMin] > x[j]:
				indexMin = j
		x[i], x[indexMin] = x[indexMin], x[i]
	return x

Java Code

void selectionSort(int[] list) {
    int indexMin, temp;

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

 

단순 삽입 정렬

• 아직 정렬되지 않은 부분의 첫번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 알고리즘
• 2번째 요소부터 선택하여 진행함
• n - 1회를 반복하여 정렬
• 셔틀 정렬이라고도 함

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

 

Python Code

def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1] = x[j]
			j = j - 1
		x[j+1] = key
	return x

Java Code

void insertionSort(int[] arr)
{

   for(int index = 1 ; index < arr.length ; index++){

      int temp = arr[index];
      int aux = index - 1;

      while( (aux >= 0) && ( arr[aux] > temp ) ) {

         arr[aux + 1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}