버블정렬을 만들다.
코드블럭<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
// 정렬 알고리즘
// 1. 버블 정렬 : 인접한 두 인자끼리 비교하여 정렬
//
let arr = [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1];
let lenArr = arr.length
// if(arr[0] > arr[1]){
// 치환: 두 변수 값을 서로 바꾸는 것
// 임시변수를 만들어서 변수값이 사라지는 것을 방지한다.
// let temp = arr[0];
// arr[0] = arr[1];
// arr[1] = temp;
// }
// console.log(arr)
// if(arr[1] > arr[2]){
// let temp = arr[1];
// arr[1] = arr[2];
// arr[2] = temp;
// }
// console.log(arr)
// if(arr[2] > arr[3]){
// let temp = arr[2];
// arr[2] = arr[3];
// arr[3] = temp;
// }
// console.log(arr)
// if(arr[3] > arr[4]){
// let temp = arr[3];
// arr[3] = arr[4];
// arr[4] = temp;
// }
// console.log(arr)
for(i = 0; i <= lenArr - 2 ; i++){
if(arr[i] > arr[i+1]){
let temp = arr[i];
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
console.log(arr)
}
console.log("ㅡㅡㅡㅡㅡ과정 1 끝ㅡㅡㅡㅡ")
for(i = 0; i <= lenArr - 3; i++){
if(arr[i] > arr[i+1]){
let temp = arr[i];
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
console.log(arr)
}
console.log("ㅡㅡㅡㅡㅡ과정 2 끝ㅡㅡㅡㅡ")
for(i = 0; i <= lenArr - 4; i++){
if(arr[i] > arr[i+1]){
let temp = arr[i];
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
console.log(arr)
}
console.log("ㅡㅡㅡㅡㅡ과정 3 끝ㅡㅡㅡㅡ")
for(i = 0; i <= lenArr - 5; i++){
if(arr[i] > arr[i+1]){
let temp = arr[i];
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
console.log(arr)
}
console.log("ㅡㅡㅡㅡㅡ과정 4 끝ㅡㅡㅡㅡ")
console.log("ㅡㅡㅡㅡㅡ최종ㅡㅡㅡㅡㅡㅡ")
for(j = lenArr - 1; j >= 0; j--){ // 3 2 1 0 / 2 3 4 5
for(i = 0; i <= (lenArr - 1) - (5 - j); i++){
if(arr[i] > arr[i + 1]){
let temp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
}
}
console.log(arr)
</script>
</body>
</html>버블 정렬 방법을 직접 for문과 if문을 응용하여 만들기를 해보자.
버블 정렬: 인접한 두 인자끼리 서로 크기 비교를 하여 서로 위치를 바꾸는 과정으로 진행되는 정렬 방식
별 찍기 했을 때처럼 버블 정렬을 오름차순으로 정렬하는 방법을 리팩토링 방법으로 설명해 보겠다.
1. 배열 선언 및 변수 선언
let arr = [4, 3, 2, 1, 0]
let lenArr = arr.length // 5나중에 쓰일지 모르는 배열의 길이는 5
2 - 1 ) 1바퀴째 정렬단계
if(arr[0] > arr[1]){
치환: 두 변수 값을 서로 바꾸는 것
임시변수를 만들어서 변수값이 사라지는 것을 방지한다.
let temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;
}
console.log(arr)
두 값을 비교하고 서로 위치를 바꾸는 과정에서 치환을 해줘야 하는데, 그 이유는 두 자리의 값을 서로 바꾸려 할 때 무조건
치환을 안 하면 무조건 한 값은 사라지게 된다. 이를 방지하기 위해 둘 중 하나를 치환하여 안전하게 자리를 변경한다.
치환: 새로운 변수에 기존에 있던 값을 넣는 것. keep 느낌
0번째 인덱스와 1번째 인덱스를 서로 비교하여 더 큰 값이 뒤로 밀려나게 코드를 짰다.
4번의 과정을 반복문으로 적은 코드이다. 반복문의 조건부까지 배열의 길이를 사용해서 일반화를 해주었다.
(일반화를 하는 이유: 배열에 새로운 수를 추가하거나 빼도 코드가 정상적으로 작동하기 위함)
조건부의 일반화 작업은 제일 마지막에 해도 되니까 일단은 안되어있다 고치고 보면 편하다.
조건부 원래 i <= 3
for (i = 0; i <= lenArr - 2; i++) {
if (arr[i] > arr[i + 1]) {
let temp = arr[i];
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
console.log(arr)
}
2 - 2) 2바퀴째 정렬단계
if(arr[1] > arr[2]){
let temp = arr[1];
arr[1] = arr[2];
arr[2] = temp;
}
console.log(arr)1바퀴째와 차이점을 보고 규칙성에 의심을 가지고 그 점을 주시해야 하는 단계이다.
일단 1번째 차이점은 arr []에 들어가는 인덱스 번호이다. 인덱스 번호가 1씩 증가하였다.
2번째 차이점은 결과를 보면 과정 횟수가 4회에서 3회로 줄어들었다.
의심을 하고 다음 단계로 넘어가겠다.
조건부 원래 i <= 2
for (i = 0; i <= lenArr - 3; i++) {
if (arr[i] > arr[i + 1]) {
let temp = arr[i];
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
console.log(arr)
}
console.log("ㅡㅡㅡㅡㅡ과정 2 끝ㅡㅡㅡㅡ")2 - 3) 3바퀴째 정렬단계
if(arr[2] > arr[3]){
let temp = arr[2];
arr[2] = arr[3];
arr[3] = temp;
}
console.log(arr)2바퀴째와 차이점을 보면 또 인덱스 번호가 1씩 증가했다.
그럼 이제 3개를 봤으니 확신을 해볼 만하다. 인덱스 번호는 반복문을 적용할 때 변수의 영향을 받겠구나.
과정 횟수도 3회에서 2회로 줄어들었다. 그럼 과정 횟수를 정하는 건 뭐지?라는 생각을 해야 한다.
for (i = 0; i <= lenArr - 4; i++) {
if (arr[i] > arr[i + 1]) {
let temp = arr[i];
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
console.log(arr)
}
console.log("ㅡㅡㅡㅡㅡ과정 3 끝ㅡㅡㅡㅡ")조건부 원래 i <= 1
2 - 4) 4바퀴째 정렬단계
if(arr[3] > arr[4]){
let temp = arr[3];
arr[3] = arr[4];
arr[4] = temp;
}
console.log(arr)인덱스 번호 1씩 증가
for (i = 0; i <= lenArr - 5; i++) {
if (arr[i] > arr[i + 1]) {
let temp = arr[i];
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
console.log(arr)
}
console.log("ㅡㅡㅡㅡㅡ과정 4 끝ㅡㅡㅡㅡ")조건부 원래 i <= 0
3) 최종 for문 작성하기
console.log("ㅡㅡㅡㅡㅡ최종ㅡㅡㅡㅡㅡㅡ")
console.log("ㅡㅡㅡㅡㅡ버블ㅡㅡㅡㅡㅡㅡ") // lenArr = 5
for (j = lenArr - 1; j >= 0; j--) { // 3 2 1 0 / 2 3 4 5
for (i = 0; i <= (lenArr - 1) - (5 - j); i++) {
if (arr[i] > arr[i + 1]) {
let temp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
}
console.log(arr)
}
전체적인 코드의 흐름
외부 for문은 총 몇바퀴를 도는지 정해주는 for문이고
내부 for문은 각각의 바퀴에서 비교하는 횟수라고 생각하면 편하다.
우리는 오름차순으로 이 배열을 정렬하려고 한다.
1바퀴째에서 제일 앞에서 인접한
- 4와 3을 비교하고 4가 더 크니까 4를 뒤로 보내고
- 또 4와 2를 비교하고 4를 뒤로 보내고
- 또또 4와 1을 비교하고 4를 뒤로 보내고
- 또또또 4와 0을 비교해서 4를 맨뒤로 보낸다
여기서! 맨 뒤로간 4는 이제 고정된다. 더 이상 건드릴 필요가 없다.
따라서 2바퀴째는 3번의 비교 과정이 생기는 것이다.
연쇄적으로 3바퀴째는 2번, 4바퀴째는 1번으로 결국 비교가 끝나며 오름차순정렬도 끝나게 된다.
라는 논리로 이 코드는 작동한다.
코드의 초기값, 조건식 설명
전체 과정은 배열의 길이와 관련이 있다. 배열의 길이 - 1 만큼 한다. (어떻게 알아? 규칙성을 찾아.)
∵ 외부 for문 초기값은 j = lenArr - 1이다. ( j든 i든 상관없다.)
줄어들어야 하니까 증감식 j-- ( 조건식은 그냥 제일 마지막에 생각하자 )
내부 for문의 초기값은 0이다. 왜냐하면 내부 for문은 인덱스의 번호와 관련이 있는데
아까 리팩토링보면 0부터 1씩 증가하니까 초기값 i = 0 증감식 i++이다.
이제 제일 중요한 조건식을 써야 할 차례인데,
내부 for문의 조건식
각각의 바퀴에서 비교하는 과정이랑 관련이 있고 또 바퀴가 증가할수록
맨 뒤에 값이 고정되는 게 늘어나니까 배열의 길이와 연관이 있다고 생각해야 한다. (몰라? 모르면 외워.)
리팩토링 과정에서 for 조건식 보면 -2 -3 -4 -5지만 사실 이건 -1 -1 / -1 -2 / -1 -3 / -1 -4이다.
(lenArr -1) -1 이런 꼴로 봐야 한다. lenArr -1은 바퀴 횟수이고 뒤에 -1 은 다음 바퀴로 넘어가면 그 바퀴 안에서의 과정은
1씩 감소하기 때문에 -1을 더 하기때문에 다음 바퀴로 갈수록 -1 → -2 → -3 → -4 가된다.
(이해하기 힘들겠지만 설명하는 것도 힘들다)
그럼 반복에 따라 -1 -2 -3 -4를 만들어내야 하는데 j를 가지고 만들어야 하고, j는 4 ~ 1
그렇다면 5 - j 가 -1 -2 -3 -4가 되지 않을까?라는 생각을 해서
내부 for문의 조건식은 (lenArr - 1) - (5 - j)라고 이해하기 쉽게 쓸 수 있다.
외부 for문의 조건식
내부 for문의 조건식을 완성했다. 리팩토링을 보면 i + 1이 최대 4가 된다. 그럼 i는 최대 3까지 커진다는 소리다. 그럼 내부 조건식의 값(i)이 3이 되려면 j = 4, 그럼 규칙성을 알아보면 2가 되려면 j = 3, 1이 되려면 j = 2, 0이면 j = 1 그럼 j는 1씩 작아지니까 최솟값을 조건식에 넣으면 된다. 그럼 j >= 1
if문은 2 -1 과정에서 설명했으니 이제 버블 정렬은 완성됐다.
내림차순은 if의 부등호만 반대로 변경하면 된다.
'Front-End > 1. JavaScript 기초' 카테고리의 다른 글
| [JS] Ex23_선택정렬.html (0) | 2023.06.15 |
|---|---|
| [JS] Ex21_가위바위보_실습.html (0) | 2023.06.15 |
| [JS] Ex20_배열함수.html (0) | 2023.06.15 |
| [JS] Ex19_배열실습.html (0) | 2023.06.15 |
| [JS] Ex18_배열.html (0) | 2023.06.14 |
