삽입정렬, 선택정렬, 버블정렬

버블정렬

인접한 숫자끼리 대소 비교를 통해 큰 수를 뒤로 이동시키는 방식의 정렬

 

# 시간복잡도

n-1, n-2 .... 1까지 총 n(n-1)/2번의 결과가 나오므로 O(n^2)의 시간복잡도를 가지게 된다.

 

# 공간복잡도

다른 공간을 활용하지 않고 현재 데이터 내에서 자리를 switch하는 것이기에 O(n)의 공간복잡도를 가지게 된다.

 

# Code

1. python

def bubbleSort(data):
  for i in range(len(data)-1):
    for j in range(len(data)-1-i):
      if data[j] > data[j+1]:
        data[j], data[j+1] = data[j+1], data[j]
  return data

public static int[] bubbleSort(int[] data) {
  for (int i = 0; i < data.length-1; i++) {
    for (int j = 0; j < data.length-1-i; j++) {
      if (data[j] > data[j+1]) {
        swap(data, j, j+1);
      }
    }
  }
  return data;
};
 
private static void swap(int[] data, int idx1, int idx2) {
  int temp = data[idx1];
  data[idx1] = data[idx2];
  data[idx2] = temp;
}

function bubbleSort(data) {
  for (let i = 0; i < data.length - 1; i++) {
    for (let j = 0; j < data.length - 1 - i; j++) {
      if (data[j] > data[j+1]) {
        [data[j], data[j+1]] = [data[j+1], data[j]]
      }
    }
  }
  return data
}

개선된 버블정렬

기존의 버블정렬의 경우 정렬 사이클을 진행하며 정렬이 완료가 되어도 모든 사이클을 다 돌아야 했다.

개선된 버블정렬 방식을 이용한다면 정렬이 완료되었을때 더는 루프를 돌지 않아도 된다.

한 사이클을 순회할때 swap이 일어나지 않았다면 더는 탐색할 필요가 없으므로 루프를 break 시켜주면 된다.

 

# 시간복잡도

이를 통해 최선의 경우인 정렬이된 경우를 생각해보면 최초 한번의 n번만큼의 순회만 하고 break 되므로 시간복잡도는 O(n)으로 개선시킬수 있다.

 

# Code

1. python

def bubbleSort(data):
  for i in range(len(data)-1):
    isSwap = false
    for j in range(len(data)-1-i):
      if data[j] > data[j+1]:
        data[j], data[j+1] = data[j+1], data[j]
        isSwap = true
    if not isSwap:
        break
  return data

2. java

public static int[] bubbleSort(int[] data) {
  for (int i = 0; i < data.length-1; i++) {
    boolean isSwap = false
    for (int j = 0; j < data.length-1-i; j++) {
      if (data[j] > data[j+1]) {
        swap(data, j, j+1);
        isSwap = true;
      }
    }
    if (!isSwap) {
        break;
    }
  }
  return data;
};
 
private static void swap(int[] data, int idx1, int idx2) {
  int temp = data[idx1];
  data[idx1] = data[idx2];
  data[idx2] = temp;
}

3.  javascript

function bubbleSort(data) {
  for (let i = 0; i < data.length - 1; i++) {
    let isSwap = false
    for (let j = 0; j < data.length - 1 - i; j++) {
      if (data[j] > data[j+1]) {
        [data[j], data[j+1]] = [data[j+1], data[j]]
        isSwap = true
      }
    }
    if (!isSwap) {
        break
    }
  }
  return data
}

 

선택정렬

0번 인덱스부터 자리를 선정한 후 그 이후 자료를 순회하며 최소값을 찾아 비교 후 switch하며 자리를 채워나가는 정렬

 

 

# 시간복잡도

비교대상 각 자리별로 for문 순회를 해야하므로 앞선 버블정렬과 마찬가지로 O(n^2)의 시간복잡도를 가지게 된다.

 

# 공간복잡도

정렬을 위해 다른 공간이 필요치 않고 현재 공간속에서 자리 swich가 일어나므로 O(n)의 공간복잡도를 가지게 된다.

 

# Code

1. python

def selectionSort(data):
  for i in range(len(data)-1):
    minIdx = i
    for j in range(i+1, len(data)):
      if data[j] < data[minIdx]:
        minIdx = j
    data[i], data[minIdx] = data[minIdx], data[i]
  return data

2. Java

public static int[] selectionSort(int[] data) {
  for (int i = 0; i < data.length-1; i++) {
    int minIdx = i;
    for (int j = i+1; j < data.length; j++) {
      if (data[minIdx] > data[j]) {
        minIdx = j;
      }
    }
    swap(data, i, minIdx);
  }
  return data;
}
 
private static void swap(int[] data, int idx1, int idx2) {
  int temp = data[idx1];
  data[idx1] = data[idx2];
  data[idx2] = temp;
}

3. Javascript

function selectionSort(data) {
  for (let i = 0; i < data.length - 1; i++) {
    let minIdx = i
    for (let j = i + 1; j < data.length; j++) {
      if (data[minIdx] > data[j]) {
        minIdx = j
      }
    }
    [data[i], data[minIdx]] = [data[minIdx], data[i]]
  }
  return data
}

삽입정렬

1번 인덱스자리에 있는 값부터 비교대상인 key값으로 두고 그 왼쪽에 있는 자료들을 탐색해 나가며 key값보다 작아지는 자료가 오는 자리에 key값을 삽입함으로서 정렬시키는 방법

 

 

# 시간복잡도

key별로 최대 n-1만큼 다시 한번 순회해야하므로 O(n^2)의 시간복잡도를 가지게 된다.

모든 자료가 정렬되어 있을 경우 key별로 순회(n)하며 비교가 단 한번만 이루어지게 되므로 O(n)의 시간복잡도를 가지게 된다.

 

# 공간복잡도

정렬을 위해 다른 공간이 필요없으므로 O(n)의 공간복잡도를 가지게 된다.

 

# Code

1. python

def insertionSort(data):
  for i in range(1, len(data)):
    key = data[i]
    for j in range(i-1, -1, -1):
      if data[j] > key:
        data[j+1], data[j] = data[j], data[j+1]
      else:
        break
  return data

2. Java

public static int[] insertionSort(int[] data) {
  for (int i = 1; i < data.length; i++) {
    int key = data[i];
    for (int j = i-1; j > -1; j--) {
      if (data[j] > key) {
        swap(data, j, j+1);
      } else {
        break;
      }
    }
  }
  return data;
}
 
private static void swap(int[] data, int idx1, int idx2) {
  int temp = data[idx1];
  data[idx1] = data[idx2];
  data[idx2] = temp;
}

3. Javascript

function insertionSort(data) {
  for (let i = 1; i < data.length; i++) {
    let key = data[i]
    for (let j = i-1; j > -1; j--) {
      if (data[j] > key) {
        [data[j+1], data[j]] = [data[j], data[j+1]]
      } else {
        break
      }
    }
  }
  return data
}