gnomeSortノームソート

引数に指定された配列をノームソートで並び替えます。

構文
gnomeSort( array )
引数
array 必須
ソートする数値を格納した配列。参照引数。
戻り値

プログラム

UWSC
//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。 
// 【戻り値】
//   
//////////////////////////////////////////////////
PROCEDURE gnomeSort(Var array[])
	DIM n = 1
	DIM num = UBound(array)
	WHILE n < num + 1
		IFB array[n-1] <= array[n] THEN
			n = n + 1
		ELSE
			swap(array[n], array[n-1])
			n = n - 1
			IF n = 0 THEN n = n + 1
		ENDIF
	WEND
FEND

//////////////////////////////////////////////////
// 【引数】
//   inputs : 繰り返す文字列 
//   multiplier : inputsを繰り返す回数 
// 【戻り値】
//   inputsをmultiplier回を繰り返した文字列を返します 
//////////////////////////////////////////////////
FUNCTION strRepeat(inputs, multiplier)
	DIM res = ""
	FOR n = 1 TO multiplier
		res = res + inputs
	NEXT
	RESULT = res
FEND

//////////////////////////////////////////////////
// 【引数】
//   a : bと交換する値。参照引数。 
//   b : aと交換する値。参照引数。 
// 【戻り値】
//   
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
	DIM tmp = a
	a = b
	b = tmp
FEND

//////////////////////////////////////////////////
// 【引数】
//   arrayname : 上限値を求める配列の名前 
//   dimension : 返す次元を示す整数 
// 【戻り値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(arrayname[], dimension = 1)
	RESULT = EVAL("RESIZE(arrayname" + strRepeat("[0]", dimension - 1) + ")")
FEND

解説

  1. 2行目
    UWSC
    	DIM n = 1
    nに1を代入。
  2. 3行目
    UWSC
    	DIM num = UBound(array)
  3. 4,12行目
    UWSC
    	WHILE n < num + 1
		…
	WEND
  4. 5,7,11行目
    UWSC
    		IFB array[n-1] <= array[n] THEN
			…
		ELSE
			…
		ENDIF
    配列のn-1番目がn番目より小さければ6行目>>>、そうでなければ8行目>>>。
  5. 6行目
    UWSC
    			n = n + 1
    次に進む。
  6. 8-10行目
    UWSC
    			swap(array[n], array[n-1])
			n = n - 1
			IF n = 0 THEN n = n + 1
    配列のn-1番目とn番目を交換する。

使い方

UWSC
DIM array[] = 8, 20, 2, 22, 17, 30, 14, 4, 25, 5

gnomeSort(array)

FOR item IN array
	PRINT item
NEXT
結果
プレーンテキスト
2
4
5
8
14
17
20
22
25
30

ノームソートとは

ノームソートはソートアルゴリズムの一つです。入力配列を1つずつ前方に走査しながら隣接する要素の大小関係を比較して、大小関係が逆であれば交換するという操作を繰り返すことでソートを行います。

最悪計算時間 \(O(n^{2})\)
最良計算時間 \(O(n)\)

アルゴリズム

  1. 最初に、配列の先頭要素をカレントポインタに設定します。
  2. カレントポインタが配列の末尾まで到達するまで、以下の処理を繰り返します。
    1. カレントポインタが指す要素と、カレントポインタの前の要素の大小関係を比較します。
    2. もし、大小関係が逆であれば2つの要素を交換し、カレントポインタを1つ前に戻します。
    3. もし、大小関係が正しければカレントポインタを1つ進めます。
  3. カレントポインタが配列の末尾まで到達したら、ソートが完了です。

この記事は役に立ちましたか？

はい
いいえ
ご協力ありがとうございます。

関連記事

QSORT関数 (スクリプト関数)
配列の中身をソートします。
small (自作関数)
配列の中で小さい方から数えた順位の値を求めます。
bubbleSort (自作関数)
引数に指定された配列を バブルソート で並び替えます。
shakerSort (自作関数)
引数に指定された配列を シェーカーソート で並び替えます。
insertionSort (自作関数)
引数に指定された配列を 挿入ソート で並び替えます。
shellSort (自作関数)
引数に指定された配列を シェルソート で並び替えます。
heapSort (自作関数)
引数に指定された配列を ヒープソート で並び替えます。
quickSort (自作関数)
引数に指定された配列を クイックソート で並び替えます。
shearSort (自作関数)
引数に指定された配列を シェアソート で並び替えます。
Sort.Header プロパティ (Excel)
最初の行にヘッダー情報が含まれるかどうかを指定します。