IOS配列並べ替え整理

IOS配列並べ替え整理

demo gitアドレス
iosのソートといえば、方法はいろいろありますが、最近はちょうど時間があって、整理をして、ついでにいろいろなソート方法の効率をテストしてみました.
テストのソート方法は主に以下のとおりです.

挿入ソート(自己実装)

クイックソート(自己実装)

swift array.sorted(by: {(Any, Any) -> Bool})

oc nsarray sortedArray(comparator: {Any, Any)->ComparisonResult})

oc nsarray sortedArray(using: [NSSortDescriptor]);

ソートの挿入

ソートロジックの挿入は簡単で,データ構造アルゴリズム解析に関する書籍ではソートの典型的なケースとして一般的に用いられる.配列を巡り、各要素を前のサイズの正しい位置に挿入し、それより大きい要素を1つ後ろに移動することが基本です.挿入ソートは、エレメントを使用する前のすべてのエレメントがソートされたという事実を利用します.挿入ソートはバブル,ヒルと同様,平均時間複雑度はO(N^2)であった.

func insertionSort(cArr:[Int])->[Int]
    {
        var arr = cArr;

        let arrLen = arr.count;

        for p in 1..let tmp = arr[p];

            for j in (0...p).reversed()
            {
                if(j-1 > -1 && arr[j-1] > tmp)
                {
                    arr[j] = arr[j-1];

                }
                else
                {
                    arr[j] = tmp;

                    break;
                }

            }
        }

        return arr;
    }

クイックソート

高速ソートは効率的な最良のソート方法の一つと考えられ,その核心思想は並列ソートと同様に,平均時間複雑度O(Nlogn)の分置アルゴリズムの実現である.

func qSort( arr:inout [Int], left:Int, right:Int)
    {
        if(right - left > 2)
        {
            let pivotIndex = Int((right - left)/2 + left);

            let pivotValue = arr[pivotIndex];

            arr[pivotIndex] = arr[right];
            arr[right] = pivotValue;

            var i:Int = left;
            var j:Int = right - 1;

            while(true)
            {
                while(arr[i] < pivotValue && i < right)
                {
                    i += 1;
                }

                while (arr[j] > pivotValue && j > left)
                {
                    j -= 1;
                }

                if(i < j)
                {
                    let tmpIValue = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmpIValue;

                    i += 1;
                    j -= 1;
                }
                else
                {
                    break;
                }
            }

            let tmpIValue = arr[i];
            arr[i] = arr[right];
            arr[right] = tmpIValue;

            qSort(arr: &arr, left: left, right: i - 1);
            qSort(arr: &arr, left: i + 1, right: right);
        }
        else if(right - left > 0)
        {
            if(arr[left] > arr[right])
            {
                let tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }

    }

    func quickSort(cArr:[Int])->[Int]
    {
        var arr = cArr;

        qSort(arr: &arr, left: 0, right: arr.count - 1);

        return arr;
    }

swift arrayソート

構造が簡単すぎて、直接コードをつけます

func swiftBlockSort(arr:[Int])->[Int]
    {
        let result = arr.sorted(by: {(a, b)->Bool in return a < b;});

        return result;
    }

NSArray sortedArray comparator

このソートには、閉パケット{(Any, Any) -> ComparisonResul}である関数にComparatorを入力する必要があります.

func ocComparatorSort(arr:NSArray)->[Any]
    {
        let result = arr.sortedArray(comparator: {
            (x, y) -> ComparisonResult in
            let a:Int = x as! Int;
            let b:Int = y as! Int;
            if(a < b)
            {
                return ComparisonResult.orderedAscending;
            }
            else if(b < a)
            {
                return ComparisonResult.orderedDescending;
            }

            return ComparisonResult.orderedSame;
            })
        return result;
    }

NSArray sortedArray NSSortDescriptor

NSArrayが提供するもう一つのソート方法はNSSortDiscriptorによる

func ocDescriptorSort(arr:NSArray)->[Any]
    {
        let sortDescriptor:NSSortDescriptor = NSSortDescriptor(key: nil, ascending: true);

        let result = arr.sortedArray(using: [sortDescriptor]);

        return result;
    }

こうりつしけん

var srcArr:[Int] = [];

    override func viewDidLoad() {
        super.viewDidLoad()
        // Do any additional setup after loading the view, typically from a nib.

        let num:Int = 10000;

        for _ in 0...num
        {
            srcArr.append(Int(arc4random())%num);
        }

    }

まず10000個の数の配列を初期化し,次にそれぞれ上の各種並べ替え方法を用いてテストを行う.
instrument time profilerの結果は次のとおりです.

Weight  Self Weight     Symbol Name
206.00 ms   23.7%   0 s        @objc ViewController.ocCompareSort(AnyObject) -> ()

189.00 ms   21.7%   0 s        @objc ViewController.onDescriptorSort(AnyObject) -> ()

164.00 ms   18.9%   0 s        @objc ViewController.insertSort(AnyObject) -> ()

60.00 ms    6.9%    0 s        @objc ViewController.swiftBlockSort(AnyObject) -> ()

48.00 ms    5.5%    0 s        @objc ViewController.quickSort(AnyObject) -> ()

複数回のテストを経て、結果は基本的に高速ソートとswift arrayソートが1つの水平線上にあるのに対し、NSArray sortedArray comparator、NSArray sortedArray NSSortDescriptor、挿入ソートが同じレベルで、基本的には前の2つのソートの3倍の時間である(Appleがswiftの最適化をこんなによくしたのだろうか?)