連結ソート
30650 ワード
連結ソートとは?
ある問題をまず小さな問題に分けて、それから元の問題に組み合わせて、
分割と征服
連結ソートについて
分割ぶんかつ[5, 10, 66, 77], [54, 32, 11, 15]
[5, 10], [66, 77], [54, 32], [11, 15]
[5], [10], [66], [77], [54], [32], [11], [15]
征服する
:グループの0番目の比較[5, 10], [66, 77], [32, 54], [11, 15]
// 1) 5와 66을 비교함
원본: [], [10], [66, 77], [32, 54], [11, 15]
결과값: [5]
// 2) 10과 66을 비교함
원본: [], [], [66, 77], [32, 54], [11, 15]
결과값: [5, 10]
// 3) [66, 77]은 이미 정렬된 상태이므로 그대로 가지고옴
원본: [], [], [], [], [32, 54], [11, 15]
결과값: [5, 10, 66, 77]
// 4) 나머지에 반복
원본: [], [], [], [], [], [], [], []
결과값: [5, 10, 66, 77], [11, 15, 32, 54]
// 다시 0번째끼리 비교
[5, 10, 66, 77], [11, 15, 32, 54]
원본: [], [], [66, 77], [], [], [], []
결과값: [5, 10, 11, 15, 32, 54]
// 남은 66, 77은 이미 정렬된 상태이므로 통째로 넣어준다.
결과값: [5, 10, 11, 15, 32, 54, 66, 77]
再帰関数を使用した集計ソート let 입력값 = [5, 10, 66, 77, 54, 32, 11, 15];
分割ぶんかつ
function 병합정렬(입력배열) {
let 입력배열의길이 = 입력배열.length;
if(입력배열의길이 <= 1) {
return 입력배열
}
let 중간값 = parseInt(입력배열의길이/2);
let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
let 그룹둘 = 병합정렬(입력배열.slice(중간값, )); // 비워두면 알아서 마지막까지 자름
return `그룹하나 : ${그룹하나} 그룹둘 : ${그룹둘}\n`
}
console.log(병합정렬(입력값));
// 결과
그룹하나 : 그룹하나 : 그룹하나 : 5 그룹둘 : 10
그룹둘 : 그룹하나 : 66 그룹둘 : 77
그룹둘 : 그룹하나 : 그룹하나 : 54 그룹둘 : 32
그룹둘 : 그룹하나 : 11 그룹둘 : 15
下図のように分割された状態です.
征服する
function 병합정렬(입력배열) {
let 입력배열의길이 = 입력배열.length;
let 결과값 = []; // 정렬된 값을 넣어줄것
if(입력배열의길이 <= 1) {
return 입력배열
}
let 중간값 = parseInt(입력배열의길이/2);
let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
let 그룹둘 = 병합정렬(입력배열.slice(중간값, ));
// 그룹하나와 그룹둘이 모두 요소가 존재할 때
while(그룹하나.length != 0 && 그룹둘.length != 0) {
if(그룹하나[0] < 그룹둘[0]) {
결과값.push(그룹하나.shift());
} else {
결과값.push(그룹둘.shift());
}
}
// 그룹하나에만 값이 있을때
while(그룹하나.length != 0) {
결과값.push(그룹하나.shift());
}
// 그룹둘에만 값이 있을때
while(그룹둘.length != 0) {
결과값.push(그룹둘.shift());
}
return 결과값;
}
console.log(병합정렬(입력값)); // [5, 10, 11, 15, 32, 54, 66, 77]
最終コード function 병합정렬(입력배열) {
let 입력배열의길이 = 입력배열.length;
let 결과값 = []; // 정렬된 값을 넣어줄것
if(입력배열의길이 <= 1) {
return 입력배열
}
let 중간값 = parseInt(입력배열의길이/2);
let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
let 그룹둘 = 병합정렬(입력배열.slice(중간값, ));
// 그룹하나와 그룹둘이 모두 요소가 존재할 때
while(그룹하나.length != 0 && 그룹둘.length != 0) {
if(그룹하나[0] < 그룹둘[0]) {
결과값.push(그룹하나.shift());
} else {
결과값.push(그룹둘.shift());
}
}
// 그룹하나에만 값이 있을때
while(그룹하나.length != 0) {
결과값.push(그룹하나.shift());
}
// 그룹둘에만 값이 있을때
while(그룹둘.length != 0) {
결과값.push(그룹둘.shift());
}
return 결과값;
}
console.log(병합정렬(입력값)); // [5, 10, 11, 15, 32, 54, 66, 77]
Reference
この問題について(連結ソート), 我々は、より多くの情報をここで見つけました
https://velog.io/@minbok/병합정렬
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
分割ぶんかつ
[5, 10, 66, 77], [54, 32, 11, 15]
[5, 10], [66, 77], [54, 32], [11, 15]
[5], [10], [66], [77], [54], [32], [11], [15]
征服する:グループの0番目の比較
[5, 10], [66, 77], [32, 54], [11, 15]
// 1) 5와 66을 비교함
원본: [], [10], [66, 77], [32, 54], [11, 15]
결과값: [5]
// 2) 10과 66을 비교함
원본: [], [], [66, 77], [32, 54], [11, 15]
결과값: [5, 10]
// 3) [66, 77]은 이미 정렬된 상태이므로 그대로 가지고옴
원본: [], [], [], [], [32, 54], [11, 15]
결과값: [5, 10, 66, 77]
// 4) 나머지에 반복
원본: [], [], [], [], [], [], [], []
결과값: [5, 10, 66, 77], [11, 15, 32, 54]
// 다시 0번째끼리 비교
[5, 10, 66, 77], [11, 15, 32, 54]
원본: [], [], [66, 77], [], [], [], []
결과값: [5, 10, 11, 15, 32, 54]
// 남은 66, 77은 이미 정렬된 상태이므로 통째로 넣어준다.
결과값: [5, 10, 11, 15, 32, 54, 66, 77]
再帰関数を使用した集計ソート let 입력값 = [5, 10, 66, 77, 54, 32, 11, 15];
分割ぶんかつ
function 병합정렬(입력배열) {
let 입력배열의길이 = 입력배열.length;
if(입력배열의길이 <= 1) {
return 입력배열
}
let 중간값 = parseInt(입력배열의길이/2);
let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
let 그룹둘 = 병합정렬(입력배열.slice(중간값, )); // 비워두면 알아서 마지막까지 자름
return `그룹하나 : ${그룹하나} 그룹둘 : ${그룹둘}\n`
}
console.log(병합정렬(입력값));
// 결과
그룹하나 : 그룹하나 : 그룹하나 : 5 그룹둘 : 10
그룹둘 : 그룹하나 : 66 그룹둘 : 77
그룹둘 : 그룹하나 : 그룹하나 : 54 그룹둘 : 32
그룹둘 : 그룹하나 : 11 그룹둘 : 15
下図のように分割された状態です.
征服する
function 병합정렬(입력배열) {
let 입력배열의길이 = 입력배열.length;
let 결과값 = []; // 정렬된 값을 넣어줄것
if(입력배열의길이 <= 1) {
return 입력배열
}
let 중간값 = parseInt(입력배열의길이/2);
let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
let 그룹둘 = 병합정렬(입력배열.slice(중간값, ));
// 그룹하나와 그룹둘이 모두 요소가 존재할 때
while(그룹하나.length != 0 && 그룹둘.length != 0) {
if(그룹하나[0] < 그룹둘[0]) {
결과값.push(그룹하나.shift());
} else {
결과값.push(그룹둘.shift());
}
}
// 그룹하나에만 값이 있을때
while(그룹하나.length != 0) {
결과값.push(그룹하나.shift());
}
// 그룹둘에만 값이 있을때
while(그룹둘.length != 0) {
결과값.push(그룹둘.shift());
}
return 결과값;
}
console.log(병합정렬(입력값)); // [5, 10, 11, 15, 32, 54, 66, 77]
最終コード function 병합정렬(입력배열) {
let 입력배열의길이 = 입력배열.length;
let 결과값 = []; // 정렬된 값을 넣어줄것
if(입력배열의길이 <= 1) {
return 입력배열
}
let 중간값 = parseInt(입력배열의길이/2);
let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
let 그룹둘 = 병합정렬(입력배열.slice(중간값, ));
// 그룹하나와 그룹둘이 모두 요소가 존재할 때
while(그룹하나.length != 0 && 그룹둘.length != 0) {
if(그룹하나[0] < 그룹둘[0]) {
결과값.push(그룹하나.shift());
} else {
결과값.push(그룹둘.shift());
}
}
// 그룹하나에만 값이 있을때
while(그룹하나.length != 0) {
결과값.push(그룹하나.shift());
}
// 그룹둘에만 값이 있을때
while(그룹둘.length != 0) {
결과값.push(그룹둘.shift());
}
return 결과값;
}
console.log(병합정렬(입력값)); // [5, 10, 11, 15, 32, 54, 66, 77]
Reference
この問題について(連結ソート), 我々は、より多くの情報をここで見つけました
https://velog.io/@minbok/병합정렬
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
let 입력값 = [5, 10, 66, 77, 54, 32, 11, 15];
function 병합정렬(입력배열) {
let 입력배열의길이 = 입력배열.length;
if(입력배열의길이 <= 1) {
return 입력배열
}
let 중간값 = parseInt(입력배열의길이/2);
let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
let 그룹둘 = 병합정렬(입력배열.slice(중간값, )); // 비워두면 알아서 마지막까지 자름
return `그룹하나 : ${그룹하나} 그룹둘 : ${그룹둘}\n`
}
console.log(병합정렬(입력값));
// 결과
그룹하나 : 그룹하나 : 그룹하나 : 5 그룹둘 : 10
그룹둘 : 그룹하나 : 66 그룹둘 : 77
그룹둘 : 그룹하나 : 그룹하나 : 54 그룹둘 : 32
그룹둘 : 그룹하나 : 11 그룹둘 : 15
function 병합정렬(입력배열) {
let 입력배열의길이 = 입력배열.length;
let 결과값 = []; // 정렬된 값을 넣어줄것
if(입력배열의길이 <= 1) {
return 입력배열
}
let 중간값 = parseInt(입력배열의길이/2);
let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
let 그룹둘 = 병합정렬(입력배열.slice(중간값, ));
// 그룹하나와 그룹둘이 모두 요소가 존재할 때
while(그룹하나.length != 0 && 그룹둘.length != 0) {
if(그룹하나[0] < 그룹둘[0]) {
결과값.push(그룹하나.shift());
} else {
결과값.push(그룹둘.shift());
}
}
// 그룹하나에만 값이 있을때
while(그룹하나.length != 0) {
결과값.push(그룹하나.shift());
}
// 그룹둘에만 값이 있을때
while(그룹둘.length != 0) {
결과값.push(그룹둘.shift());
}
return 결과값;
}
console.log(병합정렬(입력값)); // [5, 10, 11, 15, 32, 54, 66, 77]
function 병합정렬(입력배열) {
let 입력배열의길이 = 입력배열.length;
let 결과값 = []; // 정렬된 값을 넣어줄것
if(입력배열의길이 <= 1) {
return 입력배열
}
let 중간값 = parseInt(입력배열의길이/2);
let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
let 그룹둘 = 병합정렬(입력배열.slice(중간값, ));
// 그룹하나와 그룹둘이 모두 요소가 존재할 때
while(그룹하나.length != 0 && 그룹둘.length != 0) {
if(그룹하나[0] < 그룹둘[0]) {
결과값.push(그룹하나.shift());
} else {
결과값.push(그룹둘.shift());
}
}
// 그룹하나에만 값이 있을때
while(그룹하나.length != 0) {
결과값.push(그룹하나.shift());
}
// 그룹둘에만 값이 있을때
while(그룹둘.length != 0) {
결과값.push(그룹둘.shift());
}
return 결과값;
}
console.log(병합정렬(입력값)); // [5, 10, 11, 15, 32, 54, 66, 77]
Reference
この問題について(連結ソート), 我々は、より多くの情報をここで見つけました https://velog.io/@minbok/병합정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol