Algorithem_Sort#
与えられた整数配列 nums は非減少順にソートされており、各数の平方の配列を非減少順にソートして返します。
QuickSort#
実装ロジック：
指定された位置の index の値 key を取り、index と index の前の数字を比較します。前の数字が後の数字より大きい場合、位置を交換します。
例えば：
[ 8 3 5 1 4 2 ]
index が1から始まり、現在の要素は3、前の要素は8、8 > 3 なので位置を交換し、配列は[ 3 8 5 1 4 2 ] になります。
次に index は2、現在の要素は5、前の要素は8、8 > 5 なので位置を交換し、配列は[ 3 5 8 1 4 2 ] になります。
次に index は3、現在の要素は1、前の要素は8、8 > 1 なので位置を交換し、配列は[ 3 5 1 8 4 2 ] になります；5 > 1 なので位置を交換し、配列は[ 3 1 5 8 4 2 ] になります；3 > 1 なので位置を交換し、配列は[ 1 3 5 8 4 2 ] になります。
次に index は4、現在の要素は4、前の要素は8、8 > 4 なので位置を交換し、配列は[ 1 3 5 4 8 2 ] になります；5 > 4 なので位置を交換し、配列は[ 1 3 4 5 8 2 ] になります。
次に index は5、現在の要素は2、前の要素は8、8 > 2 なので位置を交換し、配列は[ 1 3 4 5 2 8 ] になります；5 > 2 なので位置を交換し、配列は[ 1 3 4 2 5 8 ] になります；4 > 2 なので位置を交換し、配列は[ 1 3 2 4 5 8 ] になります；3 > 2 なので位置を交換し、配列は[ 1 2 3 4 5 8 ] になります；1 < 2 なので停止します。
コードは以下の通りです：
class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
// 最初に、平方リストを取得します
var squareNums = nums.map({ $0 * $0 })
for j in 0..<squareNums.count {
let key = squareNums[j]
var i = j - 1
while (i >= 0 && squareNums[i] > key) {
squareNums[i+1] = squareNums[i]
i = i - 1
}
squareNums[i+1] = key
}
return squareNums
}
}
Selection Sort#
実装ロジック：
配列を走査して最小の値を見つけ、結果配列の index 0 の位置に置きます；
配列を走査して 2 番目に小さい値を見つけ、結果配列の index 1 の位置に置きます；
...
コードは以下の通りです：
class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
// 最初に、平方リストを取得します
var squareNums = nums.map({ $0 * $0 })
// selectionSort
let count = squareNums.count
for i in 0..<(count-1) {
var j_min = i
var j = i+1
// i から始まる最小の要素の index を見つけるために走査します
while (j < count) {
if squareNums[j] < squareNums[j_min] {
j_min = j
}
j = j + 1
}
// i と最小の index が異なる場合、2つの位置の要素を交換します
if i != j_min {
squareNums.swapAt(i, j_min)
}
}
return squareNums
}
}
Bubble Sort#
ロジックは以下の通りです：
隣接する 2 つの要素を順に走査し、前の要素が大きい場合は位置を交換します；その後、後ろを比較し続けます；
上記の手順を繰り返します
さらに上記の手順を繰り返します
...
交換可能な位置の要素がなくなるまで続けます
以下に例を示します：
[2, 1, 6, 4, 7, 5]
最初の走査：
index = 1; 現在の要素は2、前の要素は1、2 < 1、位置を交換、[1, 2, 6, 4, 7, 5]
index = 2; 現在の要素は6、前の要素は2、6 > 2、交換の必要なし
index = 3; 現在の要素は4、前の要素は6、4 < 6、位置を交換、[1, 2, 4, 6, 7, 5]
index = 4; 現在の要素は7、前の要素は6、7 > 6、交換の必要なし
index = 5; 現在の要素は5、前の要素は7、5 < 7、位置を交換、[1, 2, 4, 6, 5, 7]
中間に交換位置があります
2回目の走査：
index = 1; 現在の要素は2、前の要素は1、2 > 1、交換の必要なし、[1, 2, 4, 6, 5, 7]
index = 2; 現在の要素は4、前の要素は2、4 > 2、交換の必要なし
index = 3; 現在の要素は6、前の要素は4、6 > 4、交換の必要なし
index = 4; 現在の要素は5、前の要素は6、5 < 6、位置を交換、[1, 2, 4, 5, 6, 7]
index = 5; 現在の要素は7、前の要素は6、7 > 6、交換の必要なし
中間に交換位置があります
3回目の走査
index = 1; 現在の要素は2、前の要素は1、2 > 1、交換の必要なし、[1, 2, 4, 5, 6, 7]
index = 2; 現在の要素は4、前の要素は2、4 > 2、交換の必要なし
index = 3; 現在の要素は6、前の要素は4、6 > 4、交換の必要なし
index = 4; 現在の要素は6、前の要素は5、6 > 5、交換の必要なし
index = 5; 現在の要素は7、前の要素は6、7 > 6、交換の必要なし
今回の走査では交換位置がありませんでしたので、走査を終了します。
コードは以下の通りです：
class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
// 最初に、平方リストを取得します
var squareNums = nums.map({ $0 * $0 })
// bubble sort
var sorted = false;
while (!sorted) {
sorted = true
for i in 1..<(squareNums.count) {
if (squareNums[i] < squareNums[i-1]) {
squareNums.swapAt(i, i-1)
sorted = false
}
}
}
return squareNums
}
}
merge sort#
実装ロジック：
配列を 2 つの半分に分割し、さらにその半分の配列を分割し続け、配列の要素数が 1 になるまで続けます。最後に分割された最小の配列を比較し、ソートして返し、再度ソートして結合します。
示意図は以下の通りです：
コードは以下の通りです：
class Solution {
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
// ソートされた結果を格納するための新しい配列を定義します
var result: [Int] = []
// 引数を可変に変えます
var mutLeft = left
var mutRight = right
// ソートを走査します
while mutLeft.count > 0 && mutRight.count > 0 {
// ソート
// 左側が小さい場合、左側の最初の要素を取り出し、結果配列に追加します；そうでなければ右側の最初の要素を取り出し、結果配列に追加します。
result.append(mutLeft[0] < mutRight[0] ? mutLeft.removeFirst() : mutRight.removeFirst())
}
// 空でない配列を結合します
result += (mutLeft.count > 0 ? mutLeft : mutRight)
// 戻り値
return result
}
func mergeSort(_ nums: [Int]) -> [Int] {
// 配列の要素数が2未満の場合、分割する必要がなく、配列を返します
if nums.count < 2 {
return nums
}
// 中間で配列を分割します
let middle = nums.count / 2
// 0から middle までの半分の配列を取得します
let leftSlice = nums[0..<middle]
// さらに分割を続けます
let subLeft = mergeSort(Array(leftSlice))
// middle 右側の半分の配列を取得します
let rightSlice = nums[middle..<nums.count]
// さらに分割を続けます
let subRight = mergeSort(Array(rightSlice))
// 分割できなくなるまで分割し、ソートして結合して返します
return merge(subLeft, subRight)
}
func sortedSquares(_ nums: [Int]) -> [Int] {
// 最初に、平方リストを取得します
var squareNums = nums.map({ $0 * $0 })
// merge sort
return mergeSort(squareNums)
}
}