본문 바로가기

2024 코드트리 방학 조별 과제

[코드트리 조별과제] 거품정렬 & 선택 정렬

https://www.codetree.ai/missions/6/problems/bubble-sort?&utm_source=clipboard&utm_medium=text

- 버블정렬: 가장 단순한 정렬 알고리즘

- 비효율적인 알고리즘 -> 성능이 좋지 않음

- 시간 복잡도 O(N^2)

구현 코드

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		int[] arr = {4, 7, 1, 8, 0};
		
		for (int i=0; i<arr.length-1; i++) {
			for (int j=0; j<arr.length-1-i; j++) {
				if (arr[j] > arr[j+1]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
			System.out.println(Arrays.toString(arr));
		}
		
	}

}
// 또 다른 구현 코드
static void bubbleSort(int[] arr) {
		for (int i=arr.length-1; i>0; i--) {
			for (int j=0; j<i; j++) {
				if (arr[j] > arr[j+1]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
	}

출력 결과

[4, 1, 7, 0, 8]

[1, 4, 0, 7, 8]

[1, 0, 4, 7, 8]

[0, 1, 4, 7, 8]


 

https://www.codetree.ai/missions/6/problems/selection-sort?&utm_source=clipboard&utm_medium=text

- 선택정렬 : 일반적인 사람들의 정렬 방법과 가장 가까운 방법

- 시간 복잡도 O(N^2)

- 가장 작은 숫자의 인덱스를 찾아서, 하나씩 바꿔주는 방법

구현 코드

import java.util.Arrays;

public class SelectionSort {

	public static void main(String[] args) {
		int[] arr = {4, 7, 1, 8, 0};
		
		for (int i=0; i<arr.length-1; i++) {
			int minIdx = i;
			for (int j=i+1; j<arr.length; j++) {
				if (arr[j] < arr[minIdx])
					minIdx = j;
			}
			
			int tmp = arr[i];
			arr[i] = arr[minIdx];
			arr[minIdx] = tmp;
			
			System.out.println(Arrays.toString(arr));
		}

	}

}

출력 결과

[0, 7, 1, 8, 4]

[0, 1, 7, 8, 4]

[0, 1, 4, 8, 7]

[0, 1, 4, 7, 8]