4つの基本的なソートアルゴリズム

選択ソート

1. 配列の中で最小の数を見つける
2. スワップ操作: 最小の数値が常に最初に来るようにします。
3. 配列の繰り返し処理
4. 以下はコードの実装です

//ループを書く
let sort = (numbers) => {
//最初の数字の位置が決まれば、最後の数字の位置も自然に決まるので、すべての数字を調べる必要はない。
 for(let i=0; i< numbers.length -1; i++){ 
 console.log(`----`) //このログがエッセンスだ
 console.log(`i: ${i}`)
 //プラスiは、元の配列の基底のインデックスの最小値を求め、そのインデックスの値を加算する関数の実装である。
 let index = minIndex(numbers.slice(i))+ i //これは絶対に見逃せないプラス要素だ。
 console.log(`index: ${index}`)
 console.log(`min: ${numbers[index]}`)
 if(index!==i){ //また、数値が最小の値かどうかを判断する必要がある。
 swap(numbers, index, i)
 console.log(`swap ${index}: ${i}`)
 console.log(numbers)
 }
}
 return numbers
}
//配列の中で最小の値を見つけ、最小の値のインデックスを返す。
let minIndex = (numbers) => {
 let index = 0
 for(let i=1; i<numbers.length; i++){
 if(numbers[i] < numbers[index]){
 index = i
 }
 }
 return index
}
//値を入れ替え、一番小さい数値を最初に配列に入れる。
let swap = (array, i, j) => {
 let temp = array[i]
 array[i] = array[j]
 array[j] = temp
}

//再帰的な記述
let min = (numbers) =>{
 if(numbers.length > 2){
 return min([numbers[0], min(numbers.slice(1))])
 }else{
 return Math.min.apply(null, numbers)
 }
}
let minIndex = (numbers) => numbers.indexOf(min(numbers))
let sort = (numbers) => {
 if(numbers.length > 2){
 let index = minIndex(numbers)
 let min = numbers[index]
 numbers.splice(index, 1)
 return [min].concat(sort(numbers))
 }else{
 return numbers[0]>numbers[1] ? numbers.reverse() : numbers
 }
}

高速ソート

1. 配列の中央の数値を基準数として設定します。
2. 左の基準数より小さい数で配列を形成し、右の基準数より大きい数で配列を形成
3. ポイント1と2を順番に実行
4. 配列の長さが2未満の場合、それは配列に直接戻ってグループ化することはできません
5. 実行図を見てみましょう

let quickShort = (numbers)=>{
 if(numbers.length<2){
 return numbers
 }
 let index = Math.floor(numbers.length/2)
 let middel = numbers.splice(index,1)[0] //spliceリターンは1つの数値の配列である。
 //この中間値を使う必要があるので[0]
 console.log(`midedl:${middel}`) //ログを取ることは非常に重要である
 let left = []
 let right=[]
 for(let i=0;i<numbers.length;i++){
 if(numbers[i]>midel){
 right.push(numbers[i])
 }else{ 
 left.push(numbers[i])
 }
 }
 console.log(`left:${left}`)
 console.log(`right:${right}`)
 //concatを使用して、左の配列、基数、右の配列を連結する。
 return quickShort(left).concat(midel, quickShort(right)) 
}
let numbers = [1,5,6,,7,,11]
quickShort(numbers)

ソート

1. 基数がないので、配列を左右に半分に分けます。
2. 配列に格納されている数が1つになるまで1を続けます。
3. 2つの配列を比較します。
4. ソートされた配列を結合します。
5. 実行図を見てみましょう

let mergeShort = (numbers)=>{
 if(numbers.length<2){ //配列の長さを決定し、2未満は直接配列に戻る。
 return numbers
 }
 //分割の目的は、2つのサイズを比較したときに1つの数値だけの配列になることであり、これはエントリーポイントを提供することと同じである。
 let left = numbers.slice(0, Math.floor(numbers.length/2))
 let right = numbers.slice( Math.floor(numbers.length/2),numbers.length)
 console.log(`left:${left}`)
 console.log(`right:${right}`)
 return merge(mergeShort(left),mergeShort(right)) 
}
//実際の操作：組み合わせのサイズを比較する
let merge = (a,b)=>{
 if(a.length === 0){ //配列aの長さが0の場合、配列bを直接返す。
 return b
 }
 if (b.length === 0){ //配列bの長さが0の場合、配列aを直接返す。
 return a
 }
 //a配列の最初の数値がb配列の最初の数値より大きいとき、最初の数値がb配列の最初の数値である配列を返す。
 return a[0]>b[0] ? [b[0]].concat(merge(a,b.splice(1))) : [a[0]].concat(merge(b,a.splice(1)))
}
let numbers = [2,9,1,7,4,,13,6] 
mergeShort(numbers)

カウントソート

1. 配列を繰り返し、各項目をハッシュテーブルに入れ、最大値をマークします。
2. ハッシュテーブルを繰り返し（0~最大値）、配列に存在する値をプッシュします。
3. 実行図を見てみましょう

let countSort = numbers=>{
 let max = 0
 let hashTable = {}
 let result = []
 for(let i=0;i<numbers.length;i++){
 if(numbers[i]>max){ //最大値を取る
 max = numbers[i]
 }
 if(!(numbers[i] in hashTable)){ //もし[i]前の操作では、ハッシュテーブルに存在しない。
 hashTable[numbers[i]] = 1 //value = 1
 }else{ //もしそれが存在するなら、それは値を作る+= 1
 hashTable[numbers[i]] +=1 
 }
 }
 for(let j=0;j<=max;j++){ //ハッシュテーブルをトラバースする
 if(j in hashTable){
 for(let i=0;i<hashTable[j];i++) //数値が2回格納された場合は、それを押し出さなければならない。
 result.push(j)
 }
 }
 return result
}
let numbers = [9,1,7,4,,,3]
countSort(numbers)

まとめ

• すべての再帰はループに変換可能
• アルゴリズムが理解しにくいときは、実行図を描く方がずっと簡単です。
• 擬似コードもアルゴリズムを理解するのにとても良い方法で、コードからデータを代入して理解することも難しくありません。
• ログ・デバッグは、アルゴリズムをコードで実装するときにエラーがたくさん見つかった場合にとても役に立ちます。
• ループを使ったコードを書くときには、境界条件を判断する必要があるなど、アルゴリズムを理解するときには気づかなかったような細部に対処する必要があり、このような細部も考慮に入れる必要があります。