[アルゴリズム] 挿入ソートの実装（AWK編）

Posted on 2017/01/28 by 下駄

Pocket

Check

挿入ソートは大本のJavascriptで関数型の比較的長めのプログラムで構築したため、その後の言語でのコーディングにかなり苦戦を強いられる事になってしまいました。
SHELLの時もそうですが、AWKでも相当の苦戦をしてしまいました。
この手のコマンド系のスクリプト言語は変数や関数の扱いが、他の言語と比べて仕様が浅いので、長めのプログラムには向いていないんですね。
でも頑張って構築してみました。

ソースコード

BEGIN{
	FS=",";
}

# 基本関数
function insertSort(numbers){
	
	# 文字列分解する
	split(numbers , data , ",");
	
	# 数値配列を最初から順番に評価していく
	for(i=2; i<=length(data); i++){
		
		# 確定数値リストを取得
		confirmLists = getConfirmLists(numbers , i);
		##print i"|"confirmLists;
		
		# 対象外の数値リストを取得
		lastLists = getLastLists(numbers , i);
		##print i"|"lastLists;
		
		split(numbers , numbers2 , ",");
		
		# 確定数値リストに対象数値が挿入される位置を取得する
		replaceNum = getInsertPlace(confirmLists , numbers2[i]);
		##print i"|"confirmLists"|""|"replaceNum;
		
		# 確定数値リストに挿入数値の挿入
		firstLists = setInsert(confirmLists , numbers2[i] , replaceNum);
		##print i"|"confirmLists"|"numbers2[i]"|"replaceNum"|"firstLists;
		
		# リストの結合
		##numbers = setUnionLists(firstLists , lastLists);
		if(lastLists == ""){
			numbers = firstLists
		}
		else{
			numbers = firstLists","lastLists;
		}
	}
	
	return numbers;
}

# 確定数値リストに対象数値が挿入される位置を取得する
function getInsertPlace(confirmLists1 , targetNum){
 	split(confirmLists1 , confirmLists2 , ",");
    num = length(confirmLists2)+1;
    for(j=0; j<length(confirmLists2); j++){
        if(targetNum < confirmLists2[j]){
            num = j;
            break;
        }
    }
    return num;
}

# 全体数値リストから確定数値リストを取得
function getConfirmLists(numbers1 , targetNum){
	for(j in arr2){
		arr2[j]="";
	}
	split(numbers1 , numbers2 , ",");
	
	num=1;
    for(j=1; j<=length(numbers2); j++){
        if(j == targetNum){
            break;
        }
        arr2[num] = numbers2[j];
        num++;
    }
    
	str = "";
	for(j=1; j<=length(arr2); j++){
		if(arr2[j]==""){continue;}
		if(str == ""){ str = arr2[j]; } else { str = str","arr2[j]; }
	}
	return str;
}

# 数値リストの挿入
function setInsert(confirmLists1 , targetNum , replaceNum){
	for(j in arr4){
		arr4[j]="";
	}
	split(confirmLists1 , confirmLists2 , ",");
    
    # 挿入操作
    num=1;
    flg=0;
    for(j=0; j<length(confirmLists2); j++){
        if(j == replaceNum){
        	arr4[num] = targetNum;
        	num++;
        	flg++;
        }
        #arr.push();
        arr4[num] = confirmLists2[j];
        num++;
    }
    # 挿入番号がnullの場合は入れ替えなし
	if(flg == 0){
	    arr4[num] = targetNum;
	}
	
    str = "";
	for(j=1; j<=length(arr4); j++){
		if(arr4[j]==""){continue;}
		if(str == ""){ str = arr4[j]; } else { str = str","arr4[j]; }
	}
	return str;
}

# リストの結合
function setUnionLists(firstLists , lastLists){
# 	split(firstLists , firstLists , ",");
# 	split(lastLists , lastLists , ",");
    #arr = [];
    if(length(firstLists) > 0){
        for(i=0; i<length(firstLists); i++){
            #arr.push(firstLists[i]);
        }
    }
    if(length(lastLists) >0){
        for(i=0; i<length(lastLists); i++){
            #arr.push(lastLists[i]);
        }
    }
    return arr;
}

# 対象外の数値リストを取得
function getLastLists(numbers1 , targetNum){
	for(j in arr3){
		arr3[j]="";
	}
	split(numbers1 , numbers2 , ",");
	num=1;
    for(j=targetNum+1; j<=length(numbers2); j++){
        arr3[num] = numbers2[j]
        num++;
    }
    str = "";
	for(j=1; j<=length(arr3); j++){
		if(arr3[j]==""){continue;}
		if(str == ""){ str = arr3[j]; } else { str = str","arr3[j]; }
	}
	return str;
}

# 実行
{
	res = insertSort($0);
	print res;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

BEGIN{

FS=",";

}

# 基本関数

function insertSort(numbers){

# 文字列分解する

split(numbers , data , ",");

# 数値配列を最初から順番に評価していく

for(i=2; i<=length(data); i++){

# 確定数値リストを取得

confirmLists = getConfirmLists(numbers , i);

##print i"|"confirmLists;

# 対象外の数値リストを取得

lastLists = getLastLists(numbers , i);

##print i"|"lastLists;

split(numbers , numbers2 , ",");

# 確定数値リストに対象数値が挿入される位置を取得する

replaceNum = getInsertPlace(confirmLists , numbers2[i]);

##print i"|"confirmLists"|""|"replaceNum;

# 確定数値リストに挿入数値の挿入

firstLists = setInsert(confirmLists , numbers2[i] , replaceNum);

##print i"|"confirmLists"|"numbers2[i]"|"replaceNum"|"firstLists;

# リストの結合

##numbers = setUnionLists(firstLists , lastLists);

if(lastLists == ""){

numbers = firstLists

}

else{

numbers = firstLists","lastLists;

}

return numbers;

}

# 確定数値リストに対象数値が挿入される位置を取得する

function getInsertPlace(confirmLists1 , targetNum){

split(confirmLists1 , confirmLists2 , ",");

num = length(confirmLists2)+1;

for(j=0; j<length(confirmLists2); j++){

if(targetNum < confirmLists2[j]){

num = j;

break;

}

return num;

}

# 全体数値リストから確定数値リストを取得

function getConfirmLists(numbers1 , targetNum){

for(j in arr2){

arr2[j]="";

}

split(numbers1 , numbers2 , ",");

num=1;

for(j=1; j<=length(numbers2); j++){

if(j == targetNum){

break;

}

arr2[num] = numbers2[j];

num++;

}

str = "";

for(j=1; j<=length(arr2); j++){

if(arr2[j]==""){continue;}

if(str == ""){ str = arr2[j]; } else { str = str","arr2[j]; }

}

return str;

}

# 数値リストの挿入

function setInsert(confirmLists1 , targetNum , replaceNum){

for(j in arr4){

arr4[j]="";

}

split(confirmLists1 , confirmLists2 , ",");

# 挿入操作

num=1;

flg=0;

for(j=0; j<length(confirmLists2); j++){

if(j == replaceNum){

arr4[num] = targetNum;

num++;

flg++;

}

#arr.push();

arr4[num] = confirmLists2[j];

num++;

}

# 挿入番号がnullの場合は入れ替えなし

if(flg == 0){

arr4[num] = targetNum;

}

str = "";

for(j=1; j<=length(arr4); j++){

if(arr4[j]==""){continue;}

if(str == ""){ str = arr4[j]; } else { str = str","arr4[j]; }

}

return str;

}

# リストの結合

function setUnionLists(firstLists , lastLists){

# split(firstLists , firstLists , ",");

# split(lastLists , lastLists , ",");

#arr = [];

if(length(firstLists) > 0){

for(i=0; i<length(firstLists); i++){

#arr.push(firstLists[i]);

}

if(length(lastLists) >0){

for(i=0; i<length(lastLists); i++){

#arr.push(lastLists[i]);

}

return arr;

}

# 対象外の数値リストを取得

function getLastLists(numbers1 , targetNum){

for(j in arr3){

arr3[j]="";

}

split(numbers1 , numbers2 , ",");

num=1;

for(j=targetNum+1; j<=length(numbers2); j++){

arr3[num] = numbers2[j]

num++;

}

str = "";

for(j=1; j<=length(arr3); j++){

if(arr3[j]==""){continue;}

if(str == ""){ str = arr3[j]; } else { str = str","arr3[j]; }

}

return str;

}

# 実行

{

res = insertSort($0);

print res;

}

実行

$ echo "10,2,12,7,16,8,13"|awk -f insertSort.awk
2,7,8,10,12,13,16

1 2	$ echo "10,2,12,7,16,8,13"\|awk -f insertSort.awk 2,7,8,10,12,13,16

解説

データを外部ファイルではなく、コマンドで受け渡し

今までは、外部ファイルに配列データをCSV形式で保存しておいてそれをデータ取り込みしていましたが、今回は、echoコマンドを使って、コマンドで受け渡し方式にしました。
これにより、柔軟に対応できるライブラリになりますね。

関数の値受け渡しにおける配列

AWKは受け渡しは基本的には文字列にしなければエラーが出るので、大本の配列データや一時的に作成する配列部分も全て文字列で行う仕様にしています。
それを配列を分解したり、変更する関数内では、受け渡された直後にsplitで文字列から配列に分解し、returnする直前で文字列形式に変換するようにしています。
AWK言語にはsplitはあるおにjoinがないという、配列には優しくない言語なので、joinに該当する処理を確定しておくと比較的便利に利用できます。
ちなみにsplitの基本構文は以下の通り

split(文字列*in , 出力配列変数*out , Delimitor-value*split);

関数チェックのためのデバッグprint

関数が多かったこととプログラムが長かったのでエラー箇所特定のためにメイン関数にprint文を書いてデバッグしていたのをわざとそのまま残しておきました。
こういうテストコードも関数化できると便利かも・・・

Tips of Rubbish

DIYとIoTをこよなく愛する、WEB関連やデジモノなどの雑多な情報ブログ