def bubble_sort(arr): end =len(arr)-1while end >0: last_swap =0for i in range(end):if arr[i] > arr[i +1]: arr[i], arr[i +1] = arr[i +1], arr[i] last_swap = i end = last_swapprint(arr)
🍇 선택정렬
전체 모든 아이템 스캔
데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복
현재 데이터의 상태 상관없이 무조건 모든 원소를 비교하고 위치를 바꿈
가장 작은 것을 선택, 비효율적
✨ 정렬방법
전체 아이템 중 가장 작은 아이템의 위치를 그 위치를 변수에 저장
5부터 차례로 확인 후 맨 처음은 5가 제일 작기때문에 위치를 변수에 저장
그 다음 2에서 2가 5보다 작으니까 위치를 변수에 저장
쭉 하다가 1이 2보다 작으니까 위치를 변수 저장
4까지 확인 후 사이클을 끝냄
⇒ 배열에서 가장 작은 숫자가 어디에 있는지 안다
그 다음 swaps(바꾸기) : 가장 작은 숫자(위치를 알지!) 그것을 첫 번째 아이템과 바꿈
그 다음 사이클을 진행시 1부터 시작하지 않음. 1은정렬된 숫자, 정렬되지 않은 부분 중에서 가장 작은 숫자를 찾음
importjava.util.ArrayList;importjava.util.Collections;importjava.util.Scanner;publicclassMain {publicArrayList<Integer> sort(ArrayList<Integer> dataList){for(int index=0; index<dataList.size()-1; index++){for(int index2 = index +1; index2 >0; index2--){if(dataList.get(index2) <dataList.get(index2-1)){Collections.swap(dataList, index2, index2-1); }else{break; } }for(int i =0; i<dataList.size(); i++) {System.out.print(dataList.get(i)+" "); }System.out.println(); }return dataList; }publicstaticvoidmain(String[] args) {ArrayList<Integer> dataList =newArrayList<Integer>();Scanner in =newScanner(System.in);int n =in.nextInt();for (int i =0; i < n; i++) {dataList.add(in.nextInt()); }Main insertion =newMain();insertion.sort(dataList); }}
다른 사람 코드
importjava.util.Scanner;publicclassMain {publicstaticvoidmain(String[] args) {// TODO Auto-generated method stubScanner scan =newScanner(System.in);int n, i, j;int arr[] =newint[101]; n =scan.nextInt();for (i =0; i < n; i++) { arr[i] =scan.nextInt(); }for (i =1; i < n; i++) {for (j = i; j >0; j--) {if (arr[j] < arr[j -1]) {int c = arr[j]; arr[j]=arr[j-1]; arr[j-1]=c; }elsebreak; }for (j =0; j < n; j++) {System.out.printf("%d ", arr[j]); }System.out.printf("\n"); } }}
✨ 예제
array = [7,5,9,0,3,1,6,2,4,8]for i inrange(1, len(array)):for j inrange(i, 0, -1):# j변수가 인덱스 i부터 1까지 1씩 감소하면서 반복하는 문법if array[j]< array[j-1]:# 한 칸 씩 왼쪽으로 이동 array[j], array[j-1]= array[j-1], array[j]else:# 자기보다 작은 데이터를 만나면 그 위치에서 멈춤breakprint(array)
💡 range의 세 번째 변수 : range의 매개변수는 3개(start, end, step)이다. 세 번째 매개변수인 step에 -1이 들어가면 start인덱스부터 시작해서 end+1인덱스까지 1씩 감소한다.
✨ 삽입정렬의 시간복잡도
시간복잡도 : $O(N^2)$
⇒ 2중 반복문을 이용하기 때문
⇒ 선택정렬보다 빨라도 시간복잡도는 같음
⇒ 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
✨ 시간복잡도가 동일한 이유는 최악의 시나리오를 보지말고, 평균 시나리오를 봐야 하기 때문
삽입 정렬, 버블 정렬, 선택 정렬 세 가지 비교
버블 정렬
맨 처음에 있는 것을 저장 후 다음 있는 것을 비교 해서 다음 것이 지금 있는 것보다 적다면 그 수를 swap함 ⇒ 이런식으로 반복
publicstaticvoidbubbleSort(int[] array) {int n =array.length;for (int i =0; i < n -1; i++) { // 모든 요소를 순회for (int j =0; j < n - i -1; j++) { // i까지는 이미 정렬되었으므로 비교할 필요가 없음if (array[j] > array[j +1]) { // 다음 요소가 현재 요소보다 작으면 교환int temp = array[j]; array[j] = array[j +1]; array[j +1] = temp; } } }}
파이썬 코드
def bubble_sort(arr): n =len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j]# 사용 예시arr = [5,3,8,2,1,4]bubble_sort(arr)print("버블 정렬 결과:", arr)
삽입 정렬
모든 데이터를 훑어봄 일단, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복
publicstaticvoidinsertionSort(int[] array) {int n =array.length;for (int i =1; i < n; i++) { // 두 번째 요소부터 시작int key = array[i]; // 현재 요소를 저장int j = i -1;while (j >=0&& array[j] > key) { // 왼쪽의 모든 요소와 비교하여 key보다 큰 값은 오른쪽으로 이동 array[j +1] = array[j]; j--; } array[j +1] = key; // key 값을 적절한 위치에 삽입 }}
파이썬 코드
def insertion_sort(arr): n =len(arr)for i in range(1, n): key = arr[i] j = i -1while j >=0 and key < arr[j]: arr[j +1] = arr[j] j -=1 arr[j +1] = key# 사용 예시arr = [5,3,8,2,1,4]insertion_sort(arr)print("삽입 정렬 결과:", arr)
선택 정렬
필요할 때만 바꿔서 효율적
두 번째 즉, 1인덱스부터 훑어봄 왜냐 첫 번째꺼는 정렬되어 있다고 생각하니까
그리고 두번째가 왼쪽을 바라보고 왼쪽이 더 크다면 바꿈
이런식으로 적절한 위치에 넣기 때문에 거의 정렬되어 있다고 판단되는 것에 좋음
publicstaticvoidselectionSort(int[] array) {int n =array.length;for (int i =0; i < n -1; i++) { // 맨 마지막 요소는 자동으로 정렬되므로 n-1까지만 순회int minIndex = i;for (int j = i +1; j < n; j++) { // i 이후의 요소들과 비교하여 최솟값의 위치를 찾음if (array[j] < array[minIndex]) { minIndex = j; } }int temp = array[minIndex]; // 최솟값을 현재 위치로 이동 array[minIndex] = array[i]; array[i] = temp; }}
파이썬 코드
def selection_sort(arr): n =len(arr)for i in range(n): min_index = ifor j in range(i+1, n):if arr[j] < arr[min_index]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i]# 사용 예시arr = [5,3,8,2,1,4]selection_sort(arr)print("선택 정렬 결과:", arr)