๋ฐ˜๊ฐ€์›Œ์š”! ํ—ˆ๋ธŒ์ž…๋‹ˆ๋‹ค!

์ €๋Š” ๊ฐœ๋ฐœ์ž๋ฅผ ํ˜„๋Œ€ ์—ฐ๊ธˆ์ˆ ์‚ฌ๋ผ๊ณ  ํ‘œํ˜„ํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ๊ฐœ๋ฐœ์„ ๊ณต๋ถ€ํ•˜๋ฉฐ ๋А๋‚€ ์ ๋“ค๊ณผ ์ด์•ผ๊ธฐ๋ฅผ ๊ธฐ๋กํ•˜๋Š” ๊ณต๊ฐ„์ž…๋‹ˆ๋‹ค.

์ž๋ฃŒ๊ตฌ์กฐ

[์ž๋ฃŒ๊ตฌ์กฐ] ๋ฒ„๋ธ”์ •๋ ฌ Bubble Sort

mmin.h 2020. 8. 4. 10:39

์•ˆ๋…•ํ•˜์„ธ์š” ์ฃผ์ธ์žฅ H์ž…๋‹ˆ๋‹ค. 

์˜ค๋Š˜์€ ๋ฒ„๋ธ”์ •๋ ฌ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. 

๋ฒ„๋ธ” ์ •๋ ฌ์€ 1~10๊นŒ์ง€์˜ ๋ฌด์งˆ์„œํ•œ ์ˆซ์ž๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค๋ผ๊ณ  ํ• ๋•Œ, 

์ž์‹ ๋ณด๋‹ค ํฐ ์ˆ˜๊ฐ€ ์™ผ์ชฝ์— ์žˆ๋‹ค๋ฉด ์ž๋ฆฌ๋ฅผ ์„œ๋กœ ๋ฐ”๊พธ๋ฉด ์–ด๋–จ๊นŒ?๋ž€ ์•„์ด๋””์–ด์—์„œ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค. 

๋ฒ„๋ธ” ์ •๋ ฌ์€ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘์—์„œ ๊ฐ€์žฅ ์‰ฝ์ง€๋งŒ ๊ฐ€์žฅ ๋น„ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž…๋‹ˆ๋‹ค.

 

์ด ๊ณผ์ •์—์„œ ๊ฐ ์‹ธ์ดํด๋งˆ๋‹ค ๊ฐ€์žฅ ํฐ ๊ฐ’์ด ๋งจ ๋’ค๋กœ ๋ณด๋‚ด์ง€๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ปดํ“จํ„ฐ ๋‚ด๋ถ€์ ์ธ ์—ฐ์‚ฐ์ด ๊ฐ€์žฅ ๋น„ํšจ์œจ์ ์œผ๋กœ 

์ผ์–ด๋‚˜๊ฒŒ ๋˜์–ด ์‹ค์ œ ์ˆ˜ํ–‰์‹œ๊ฐ„์ด ๊ฐ€์žฅ ๋А๋ฆฐ ์•ˆ ์ข‹์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. 

 

์‹œ๊ฐ„๋ณต์žก๋„๋Š” ์„ ํƒ์ •๋ ฌ, ์‚ฝ์ž…์ •๋ ฌ๊ณผ ๋™์ผํ•œ O(N^2)์ž…๋‹ˆ๋‹ค.

 

#include <stdio.h>

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