개발일기🌷

1. 삽입정렬(Insertion Sort) 알고리즘

• 필요할 때만 각 데이터를 적절한 위치에 삽입하는 정렬(앞에 있는 원소들이 이미 정렬되어 있다고 가정)
  → 무조건 위치를 교환하는 버블 정렬, 선택 정렬에 비해 다소 효율적
• 두번째 원소부터 시작하여 그 앞의 원소들과 비교해 삽입할 위치를 지정한 후 원소를 뒤로 옮기고
  지정된 자리에 자료를 삽입하여 정렬하는 알고리즘

2. 삽입정렬 알고리즘의 구현

// Algorithm Analysis
// 삽입 정렬(Insertion Sort) : (필요할 때만)각 데이터를 적절한 위치에 삽입한다.

#include <stdio.h>
#include <stdlib.h>

int main() {
	int i, j, temp;
	int arr[10] = { 1, 9, 4, 6, 11, 10, 3, 15, 2, 13 };
	for (i = 0; i < 9; i++) {
		j = i;
		while (j >= 0 && arr[j] > arr[j + 1]) {
			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
			j--;
		}
	}
	for (i = 0; i < 10; i++)
		printf("%d ", arr[i]);

	return 0;
}

3. 삽입정렬 알고리즘의 특징

3-1. 장점

• 안정적인 정렬방법(중복된 키 값의 순서가 정렬 후에도 유지되기 때문)
• 레코드 수가 적을 경우 알고리즘 자체가 매우 간단해 다른 정렬보다 유리할 수 있음
• 대부분 레코드가 이미 정렬되어 있는 경우 매우 효율적
• 버블 정렬이나 선택 정렬에 비해 상대적으로 빠름

3-2. 단점

• 비교적 많은 레코드들의 이동을 포함
• 레코드 수가 많고 레코드 크기가 클 경우 부적합하다.

1. 선택정렬(Selection Sort) 알고리즘

• 제자리 정렬(in-place sorting) 알고리즘의 하나
  → merge sort나 quick sort처럼 요소분할시 추가적인 공간이 필요하지 않은 정렬. 버블, 삽입, 선택정렬 등
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떠한 원소를 넣을지 선택하는 알고리즘

• 주어진 배열 중 최소값을 찾는다.
• 그 값을 맨 앞에 위치한 값과 교체
• 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체
• 하나의 원소만 남을 때까지 위 방법을 반복

2. 선택정렬 알고리즘의 구현

# include <stdio.h>
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
# define MAX_SIZE 5

// 선택 정렬
void selection_sort(int list[], int n){
  int i, j, least, temp;

  // 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복한다.
  for(i=0; i<n-1; i++){
    least = i;

    // 최솟값을 탐색한다.
    for(j=i+1; j<n; j++){
      if(list[j]<list[least])
        least = j;
    }

    // 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
    if(i != least){
        SWAP(list[i], list[least], temp);
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {9, 6, 7, 3, 5};

  // 선택 정렬 수행
  selection_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

3. 선택정렬 알고리즘의 특징

3-1. 장점

• 구현이 쉽다.
• 자료 이동 횟수가 미리 결정됨.
• 비교하는 횟수에 비해 교환이 적게 일어남.

3-2. 단점

• 안정성을 만족하지 않는다.
  → 값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있다.
• 시간이 오래 걸려 비효율
  → 버블정렬에 비해 조금 더 빠른 정렬방식

1. 버블정렬(bubble sort) 알고리즘

• 서로 인접한 두 원소를 비교하여 더 작은 값을 앞으로 보내어 정하는 알고리즘
• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환
• 선택 정렬과 기본 개념이 유사
  → 버블정렬 : 요소를 교환 정렬 / 안정적 알고리즘 / 속도느림 / 간단하고 비효율적
  → 선택정렬 : 요소를 선택하여 정렬 / 불안정한 알고리즘 / 버블정렬에 비해 빠름 / 효율적
  ※ 알고리즘은 목록이나 배열에서 정렬 전 발생하는 동일한 순서로 동일한 키가 있는 요소가 안정적이라 간주

2. 버블정렬 알고리즘의 구현

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를 비교 …

이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬.

#include <stdio.h>
#include <stdlib.h>

int main() {
	int i, j, temp;
	int arr[10] = { 1, 9, 4, 6, 11, 10, 3, 15, 2, 13 };
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 9 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	for (i = 0; i < 10; i++)
		printf("%d ", arr[i]);

	return 0;
}

3. 버블정렬 알고리즘의 특징

3-1. 장점

• 구현이 간단하다.

3-2. 단점

• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
• 연산 수가 가장 많아 알고리즘 중에서 상대적으로 가장 느리고 효율성이 떨어지는 정렬방식.

→ 일반적으로 자료의 교환작업(SWAP)이 자료의 이동작업(MOVE)보다 더 복잡하기 때문에     
버블정렬은 단순성에도 불구하고 거의 쓰이지 않음