[알고리즘] 정렬(버블, 선택, 삽입)

버블정렬

*정의: 리스트 혹은 배열의 인접한 두 요소를 비교하여 정렬하는 방식. 첫번째 요소부터 마지막 요소까지 정렬을 진행하고 마지막 요소를 제외한 나머지 리스트로 모든 요소가 정렬될 때까지 같은 작업을 반복한다. 

 

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

 

예시(오름차순)

1. 두 요소의 크기 비교 후 더 큰 숫자가 뒤에 가도록 두 숫자의 위치를 바꾼다.  

 2. 그 후 다음 요소에 대해서도 1의 작업을 진행. 리스트의 마지막에 도달할 때까지 반복한다.

 

3. 마지막 요소까지 진행하면 리스트의 마지막에는 가장 큰 숫자가 위치하게 된다. 

이후 앞의 과정을 다시 반복하면 모든 숫자가 정렬된다.

 

코드

C

//list는 정렬해야 할 데이터, n은 배열의 크기를 의미
int* bubble_sort(int list[], int n){
  int i, j, temp;

  for(i=n-1; i>0; i--){
    // 1 ~ (i-1)까지 반복
    for(j=0; j<i; j++){
      // j번째가 j+1번째의 요소보다 크면 교환
      if(list[j]<list[j+1]){
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
  return list;
}

python

##list_p는 정렬한 데이터가 담긴 리스트
def bubble_Sort(list_p):
	length = list_p(x)-1
	for i in range(length):
		for j in range(length-i):
			if lis_p[j] > lis_p[j+1]:
				list_p[j], list_p[j+1] = list_p[j+1], list_p[j]
	return list_p

 

삽입정렬

정의: 각 요소를 적절한 위치에 삽입하여 실행하는 정렬이다. 먼저 배열의 첫 번째 요소를 key값으로 정하고 왼쪽 영역의 수들과 크기를 비교한 뒤 적절한 위치에 삽입한다. 그후 다음 위치에 있는 요소가 key값이 되어 앞의 작업을 수행한다. 리스트의 마지막 요소까지 이 작업을 수행하면 정렬이 완료된다.  

 

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

 

예시(오름차순)

코드

C

//list: 정렬한 데이터, n: list의 크기 
int* insertion_sort ( int *list, int n )
{
  int i, j, key;
  for ( i = 1; i < n; i++ )
  {
  	j = i
    key = list[i];
    //왼쪽에 있는 요소들과 key값의 크기를 비교하여 위치 탐색
    while ( --j >= 0 && key < data[j] ){
        list[j+1] = list[j];
    }
    //key값 삽입
    list[j+1] = key;
  }
  return list[];
}

python

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

 

 

 

선택정렬

정의: 최솟값을 찾아 순서대로 정렬하는 방법이다. 리스트에서 최소값을 찾아 리스트의 맨 앞에 삽입하고 남아있는 리스트로 같은 작업을 반복한다. 

 

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

 

코드

C

int* selection_sort(int *list, int n)
{
    int i, j, Min, temp;

    for (i = 0; i < n - 1; i++)
    {
        //연재 index 저장 
        Min = i;
        //오른쪽의 요소들과 비교하여 최소값을 찾는다.
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[Min])
            {
                Min = j;
            }
        }
        //현재 index i와 최소값 요소의 위치 교환
        temp = list[Min];
        list[Min] = list[i];
        list[i] = temp;
    }
    return list[];
}

python

def selection_sort(list_p):
	length = len(list_p)
	for i in range(length-1):
	    Min = i
		for j in range(i+1, length):
			if list_p[Min] > list_p[j]:
				Min = j
		list_p[i], list_p[Min] = list_p[Min], list_p[i]
	return list_p