# ๊ฑฐํ’ˆ ์ •๋ ฌ(Bubble Sort)


# Goal


  • Bubble Sort์— ๋Œ€ํ•ด ์„ค๋ช…ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Bubble Sort ๊ณผ์ •์— ๋Œ€ํ•ด ์„ค๋ช…ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Bubble Sort์„ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Bubble Sort์˜ ์‹œ๊ฐ„๋ณต์žก๋„์™€ ๊ณต๊ฐ„๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค.

# Abstract


Bubble Sort๋Š” Selection Sort์™€ ์œ ์‚ฌํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ์„œ๋กœ ์ธ์ ‘ํ•œ ๋‘ ์›์†Œ์˜ ๋Œ€์†Œ๋ฅผ ๋น„๊ตํ•˜๊ณ , ์กฐ๊ฑด์— ๋งž์ง€ ์•Š๋‹ค๋ฉด ์ž๋ฆฌ๋ฅผ ๊ตํ™˜ํ•˜๋ฉฐ ์ •๋ ฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ด๋‹ค.

์ด๋ฆ„์˜ ์œ ๋ž˜๋กœ๋Š” ์ •๋ ฌ ๊ณผ์ •์—์„œ ์›์†Œ์˜ ์ด๋™์ด ๊ฑฐํ’ˆ์ด ์ˆ˜๋ฉด์œผ๋กœ ์˜ฌ๋ผ์˜ค๋Š” ๋“ฏํ•œ ๋ชจ์Šต์„ ๋ณด์ด๊ธฐ ๋•Œ๋ฌธ์— ์ง€์–ด์กŒ๋‹ค๊ณ  ํ•œ๋‹ค.

# Process (Ascending)


  1. 1ํšŒ์ „์— ์ฒซ ๋ฒˆ์งธ ์›์†Œ์™€ ๋‘ ๋ฒˆ์งธ ์›์†Œ๋ฅผ, ๋‘ ๋ฒˆ์งธ ์›์†Œ์™€ ์„ธ ๋ฒˆ์งธ ์›์†Œ๋ฅผ, ์„ธ ๋ฒˆ์งธ ์›์†Œ์™€ ๋„ค ๋ฒˆ์งธ ์›์†Œ๋ฅผ, โ€ฆ ์ด๋Ÿฐ ์‹์œผ๋กœ (๋งˆ์ง€๋ง‰-1)๋ฒˆ์งธ ์›์†Œ์™€ ๋งˆ์ง€๋ง‰ ์›์†Œ๋ฅผ ๋น„๊ตํ•˜์—ฌ ์กฐ๊ฑด์— ๋งž์ง€ ์•Š๋Š”๋‹ค๋ฉด ์„œ๋กœ ๊ตํ™˜ํ•œ๋‹ค.
  2. 1ํšŒ์ „์„ ์ˆ˜ํ–‰ํ•˜๊ณ  ๋‚˜๋ฉด ๊ฐ€์žฅ ํฐ ์›์†Œ๊ฐ€ ๋งจ ๋’ค๋กœ ์ด๋™ํ•˜๋ฏ€๋กœ 2ํšŒ์ „์—์„œ๋Š” ๋งจ ๋์— ์žˆ๋Š” ์›์†Œ๋Š” ์ •๋ ฌ์—์„œ ์ œ์™ธ๋˜๊ณ , 2ํšŒ์ „์„ ์ˆ˜ํ–‰ํ•˜๊ณ  ๋‚˜๋ฉด ๋์—์„œ ๋‘ ๋ฒˆ์งธ ์›์†Œ๊นŒ์ง€๋Š” ์ •๋ ฌ์—์„œ ์ œ์™ธ๋œ๋‹ค. ์ด๋ ‡๊ฒŒ ์ •๋ ฌ์„ 1ํšŒ์ „ ์ˆ˜ํ–‰ํ•  ๋•Œ๋งˆ๋‹ค ์ •๋ ฌ์—์„œ ์ œ์™ธ๋˜๋Š” ๋ฐ์ดํ„ฐ๊ฐ€ ํ•˜๋‚˜์”ฉ ๋Š˜์–ด๋‚œ๋‹ค.

# Java Code (Ascending)


void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length; i++) {       // 1.
		for(int j= 1 ; j < arr.length-i; j++) { // 2.
			if(arr[j-1] > arr[j]) {             // 3.
                // swap(arr[j-1], arr[j])
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}
  1. ์ œ์™ธ๋  ์›์†Œ์˜ ๊ฐฏ์ˆ˜๋ฅผ ์˜๋ฏธํ•œ๋‹ค. 1ํšŒ์ „์ด ๋๋‚œ ํ›„, ๋ฐฐ์—ด์˜ ๋งˆ์ง€๋ง‰ ์œ„์น˜์—๋Š” ๊ฐ€์žฅ ํฐ ์›์†Œ๊ฐ€ ์œ„์น˜ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํ•˜๋‚˜์”ฉ ์ฆ๊ฐ€์‹œ์ผœ์ค€๋‹ค.

  2. ์›์†Œ๋ฅผ ๋น„๊ตํ•  index๋ฅผ ๋ฝ‘์„ ๋ฐ˜๋ณต๋ฌธ์ด๋‹ค. j๋Š” ํ˜„์žฌ ์›์†Œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ณ , j-1์€ ์ด์ „ ์›์†Œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ฒŒ ๋˜๋ฏ€๋กœ, j๋Š” 1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๊ฒŒ ๋œ๋‹ค.

  3. ํ˜„์žฌ ๊ฐ€๋ฅดํ‚ค๊ณ  ์žˆ๋Š” ๋‘ ์›์†Œ์˜ ๋Œ€์†Œ๋ฅผ ๋น„๊ตํ•œ๋‹ค. ํ•ด๋‹น ์ฝ”๋“œ๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์ด๋ฏ€๋กœ ํ˜„์žฌ ์›์†Œ๋ณด๋‹ค ์ด์ „ ์›์†Œ๊ฐ€ ๋” ํฌ๋‹ค๋ฉด ์ด์ „ ์›์†Œ๊ฐ€ ๋’ค๋กœ ๊ฐ€์•ผํ•˜๋ฏ€๋กœ ์„œ๋กœ ์ž๋ฆฌ๋ฅผ ๊ตํ™˜ํ•ด์ค€๋‹ค.


# GIF๋กœ ์ดํ•ดํ•˜๋Š” Bubble Sort


img (opens new window)


# ์‹œ๊ฐ„๋ณต์žก๋„


์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐํ•˜๋ฉด, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2์ด๋ฏ€๋กœ, O(n^2) ์ด๋‹ค. ๋˜ํ•œ, Bubble Sort๋Š” ์ •๋ ฌ์ด ๋ผ์žˆ๋˜ ์•ˆ๋ผ์žˆ๋˜, 2๊ฐœ์˜ ์›์†Œ๋ฅผ ๋น„๊ตํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ตœ์„ , ํ‰๊ท , ์ตœ์•…์˜ ๊ฒฝ์šฐ ๋ชจ๋‘ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(n^2) ์œผ๋กœ ๋™์ผํ•˜๋‹ค. (๊ฐœ์„ ๋œ Bubble Sort๊ฐ€ ์กด์žฌํ•˜๊ธด ํ•˜๋‚˜, ๊ธฐ์ดˆ๋ฅผ ๋‹ค์ง€๊ธฐ ์œ„ํ•œ ํ•™์Šต์ด๋ฏ€๋กœ ๋„˜์–ด๊ฐ€๊ฒ ์Œ)


# ๊ณต๊ฐ„๋ณต์žก๋„


์ฃผ์–ด์ง„ ๋ฐฐ์—ด ์•ˆ์—์„œ ๊ตํ™˜(swap)์„ ํ†ตํ•ด, ์ •๋ ฌ์ด ์ˆ˜ํ–‰๋˜๋ฏ€๋กœ O(n) ์ด๋‹ค.


# ์žฅ์ 


  • ๊ตฌํ˜„์ด ๋งค์šฐ ๊ฐ„๋‹จํ•˜๊ณ , ์†Œ์Šค์ฝ”๋“œ๊ฐ€ ์ง๊ด€์ ์ด๋‹ค.

  • ์ •๋ ฌํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฐฐ์—ด ์•ˆ์—์„œ ๊ตํ™˜ํ•˜๋Š” ๋ฐฉ์‹์ด๋ฏ€๋กœ, ๋‹ค๋ฅธ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ํ•„์š”๋กœ ํ•˜์ง€ ์•Š๋‹ค. => ์ œ์ž๋ฆฌ ์ •๋ ฌ(in-place sorting)

  • ์•ˆ์ • ์ •๋ ฌ(Stable Sort) ์ด๋‹ค.


# ๋‹จ์ 


  • ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ ์ตœ์•…, ์ตœ์„ , ํ‰๊ท  ๋ชจ๋‘ O(n^2)์œผ๋กœ, ๊ต‰์žฅํžˆ ๋น„ํšจ์œจ์ ์ด๋‹ค.

  • ์ •๋ ฌ ๋ผ์žˆ์ง€ ์•Š์€ ์›์†Œ๊ฐ€ ์ •๋ ฌ ๋์„๋•Œ์˜ ์ž๋ฆฌ๋กœ ๊ฐ€๊ธฐ ์œ„ํ•ด์„œ, ๊ตํ™˜ ์—ฐ์‚ฐ(swap)์ด ๋งŽ์ด ์ผ์–ด๋‚˜๊ฒŒ ๋œ๋‹ค.


# Conclusion


์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘์— ๊ฐ€์žฅ ์ง๊ด€์ ์ธ Bubble Sort์— ๋Œ€ํ•ด ์•Œ์•„๋ดค๋‹ค. ๊ธฐ์ˆ  ๋ฉด์ ‘์—์„œ๋„ ์ข…์ข… ๋‚˜์˜ค๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ์•Œ์•„๋‘๋ฉด ์ข‹๋‹ค.

# [์ฐธ๊ณ  ์ž๋ฃŒ]

์ตœ์ข… ์ˆ˜์ • : 7/5/2021, 1:47:28 PM