線形リスト（双方向）のソートの方法を教えてください。

双方向リストを用いて、キャラクター（名前、キャラクター番号）のリストを作成するコードを作っています。
登録したリストの、
①登録順ソート（キャラクター登録時に随時1から順に付加するキャラクター番号を利用）と、
②名前順リスト（アルファベット、漢字、ひらがな、全ての入力に対応）
を作りたいのですが、上手くいきません。

~~①についてはバブルソートで作りたいです。~~
バブルソートにこだわりはありません。自分がバブルソートしか使ったことがないため、初めにこう書きました。
以下に新たに作ってみた選択ソートでの並び替えをコードも載せておきます。
↓正直しっくり来ていません。

C++
1// 登録順に並び替え
2CharaList *sortListOrderRegist( CharaList *pList )
3{
4	if( nullptr == pList ){  // 異常系
5		return nullptr;
6	}
7
8	CharaNode *pTargetNode;
9	CharaNode *pUnsortNode;
10	CharaNode *pMax;
11	CharaNode *pPrevMax;
12	CharaNode *pSortNode = NULL;
13
14	pUnsortNode = pList->pHead;
15	while( NULL != pUnsortNode ){
16		pMax = pUnsortNode;
17		pPrevMax = NULL;
18		pTargetNode = pUnsortNode;
19		for( pTargetNode = pUnsortNode; NULL != pTargetNode->pNext; pTargetNode = pTargetNode->pNext ){
20			// 最大値要素と比較対象要素を比較する
21			if( pTargetNode->pNext->nCharaNum > pMax->nCharaNum ){
22				// 最大値要素の更新
23				pMax = pTargetNode->pNext;
24				pPrevMax = pTargetNode;
25			}
26		}
27
28		// 最大値要素を未ソートリストから削除 
29		if( NULL == pPrevMax ){
30			pUnsortNode = pMax->pNext;
31		}
32		else {
33			pPrevMax->pNext = pMax->pNext;
34		}
35
36		// 最大値要素をソート済リストの先頭に追加
37		if( NULL == pSortNode ){
38			pSortNode = pMax;
39			pMax->pNext = NULL;
40		}
41		else {
42			pSortNode->pPrev = pMax;
43			pMax->pNext = pSortNode;
44			pSortNode = pMax;
45		}
46	}
47	if( NULL != pSortNode ){
48		pSortNode->pPrev = NULL;
49	}
50	pList->pHead = pSortNode;
51}
52
53
54// 名前順に並び替え
55CharaList *sortListOrderName( CharaList *pList )
56{
57	if( nullptr == pList ){ //異常系
58		return nullptr;
59	}
60
61	CharaNode *pTargetNode;
62	CharaNode *pUnsortNode;
63	CharaNode *pMax;
64	CharaNode *pPrevMax;
65	CharaNode *pSortNode = NULL;
66
67	pUnsortNode = pList->pHead;
68	while( NULL != pUnsortNode ){
69		pMax = pUnsortNode;
70		pPrevMax = NULL;
71		pTargetNode = pUnsortNode;
72		for( pTargetNode = pUnsortNode; NULL != pTargetNode->pNext; pTargetNode = pTargetNode->pNext ){
73			// 最大値要素と比較対象要素を比較する
74			if( pTargetNode->pNext->strName > pMax->strName ){
75				/* 最大値要素の更新 */
76				pMax = pTargetNode->pNext;
77				pPrevMax = pTargetNode;
78			}
79		}
80
81		// 最大値要素を未ソートリストから削除
82		if( NULL == pPrevMax ){
83			pUnsortNode = pMax->pNext;
84		}
85		else {
86			pPrevMax->pNext = pMax->pNext;
87		}
88
89		// 最大値要素をソート済リストの先頭に追加
90		if( NULL == pSortNode ){
91			pSortNode = pMax;
92			pMax->pNext = NULL;
93			pMax->pPrev = NULL;
94		}
95		else {
96			pSortNode->pPrev = pMax;
97			pMax->pNext = pSortNode;
98			pSortNode = pMax;
99		}
100	}
101	if( NULL != pSortNode ){
102		pSortNode->pPrev = NULL;
103	}
104	pList->pHead = pSortNode;
105}

以下、リスト構造の定義になります。

C++
1typedef struct CharacterStatus{
2	string strName;
3	int nCharaNum;  // 登録順ソートのため
4　　  char chFurigana[256]; // 名前順ソートで利用する---
5	CharacterStatus *pPrev;
6	CharacterStatus *pNext;
7} CharaNode;
8
9typedef struct CharacterNodeList{
10	CharaNode *pHead;  // 先頭のノードを指すポインタ
11	CharaNode *pTail;  // 末尾のノードを指すポインタ
12} CharaList;

②について、ひらがなに限定した場合のコードを書いてみたので、これを利用して漢字、アルファベットにも対応させたいです。
以下、(単方向で書いてみた)コードになります。

C++
1CharaList *sortListAscendingOrderByName( CharaList *pList )
2{	
3	if( nullptr == pList ){//異常系
4		return nullptr;
5	}
6	
7	int nNumberOfNodes = 0;
8	//ノード数を数える
9	for( CharaNode *pCurrent = pList->pHead; pCurrent != nullptr; pCurrent = pCurrent->pNext ){
10		nNumberOfNodes++;
11	}
12	//ノードが0個、1個の場合は処理せず終了
13	if( nNumberOfNodes < 2 ){
14		return pList;
15	}
16	//ノードが2個の場合
17	else if( 2 == nNumberOfNodes ){
18		//strcmp(s1, s2)の戻り値: s1 > s2 で正の値、s1 < s2 で負の値、s1 = s2で 0 を返す。
19		if( 0 < strcmp( pList->pHead->chFurigana, pList->pHead->pNext->chFurigana ) ){
20			//入れ替え用の仮ポインタpTentative
21			CharaNode *pTemporary = pList->pHead->pNext;
22			pList->pHead->pNext = nullptr;
23			pTemporary->pNext = pList->pHead;
24			pList->pHead = pTemporary;
25			pList->pTail = pList->pHead->pNext;
26			return pList;
27		}
28	}
29	//ノードが3個以上の場合
30	else{
31		while( nNumberOfNodes > 1 ){
32			//(1)最初の2つのノードの入れ替え((2)では出来ないのでここで行う)
33			if( 0 < strcmp( pList->pHead->chFurigana, pList->pHead->pNext->chFurigana ) ){
34				CharaNode *pTemporary = pList->pHead->pNext;
35				pList->pHead->pNext = pTemporary->pNext;
36				pTemporary->pNext = pList->pHead;
37				pList->pHead = pTemporary;
38			}
39			//(2)pCurrentが指すノードの1つ先と2つ先のノードを比較し入れ替える
40			CharaNode *pCurrent = pList->pHead;
41			for( int i = 0; i < nNumberOfNodes - 2; i++ ){
42				if( 0 < strcmp( pCurrent->pNext->chFurigana, pCurrent->pNext->pNext->chFurigana ) ){
43					//(2-1)最後の2つのノードの入れ替え
44					if( nullptr == pCurrent->pNext->pNext->pNext ){
45						CharaNode *pTemporary = pCurrent->pNext;
46						pCurrent->pNext = pTemporary->pNext;//
47						pTemporary->pNext = nullptr;
48						pCurrent->pNext->pNext = pTemporary;
49						pList->pTail = pTemporary;
50					}
51					//(2-2)中間の2つのノードの入れ替え
52					else {
53						CharaNode *pTemporary = pCurrent->pNext;
54						pCurrent->pNext = pTemporary->pNext;
55						pTemporary->pNext = pCurrent->pNext->pNext;
56						pCurrent->pNext->pNext = pTemporary;
57					}
58				}
59				pCurrent = pCurrent->pNext;
60			}//end for
61			nNumberOfNodes--;
62		}//end while
63		return pList;
64	}//end if(nNodeNumber)
65}

アドバイス、改善点、見本となるコードなど教えていただきたいです。
よろしくお願いいたします。

kazuma-s

2022/06/06 16:15

pCurrent->pNext->chFurigana で、pCurrent は CharaList へのポインタ、 pCurrent->pNext は CharaNode へのポインタというのは分かるのですが、 chFurigana が何か分かりません。 strcmp で比較するということは char へのポインタのはずですが、どこにも記述がありません。質問への追記をお願いします。また、実際のテストデータでどういう結果になるのですか？

BeatStar

2022/06/06 23:01

どうしてもバブルソートですか？割と厳しいですよ、それ。というか、なぜ今回の質問が出てきたのでしょうか？課題として？それとも自分の作品内での機能として？

episteme

2022/06/07 04:13

C++なら std::list 使えばコード書かずに済むんだが...課題もしくはトレーニングが目的ですか?

dodox86

2022/06/07 07:56

コードを見るに、string(std::string)以外はもうC言語ですね。ワイド文字のstd::wstring をうまく使えるようにすれば「アルファベット、漢字、ひらがな」もほぼいけるようになる気がしますが。あえて苦難の道を選んでいるように思うので、与えられた課題なのか自分で選んだ問題なのか示すと、より回答もいただきやすいかもしれません。学校の課題のようなものだと、回答は避けられがちです。

don

2022/06/07 13:39

リスト構造体について学び始めたばかりのため、トレーニングが目的です。バブルソートにこだわりはありませんが、バブルソート以外使ったことがなくて.... ほかに良い方法があれば、完全なコードがなくても構いませんので、導入部分だけでもご教授願いたいです。

行動規範の内容に同意します

回答2件

ベストアンサー

挿入ソートを使うと、機能ごとにきれいに関数分割できます。

c++
1// pPosの後ろにpNodeを追加(pPosがnullptrなら先頭に追加)
2void add_after(CharaList* pList, CharaNode* pPos, CharaNode* pNode) {
3	CharaNode*& pNext = (pPos) ? pPos->pNext : pList->pHead;
4	CharaNode*& pPrev = (pNext) ? pNext->pPrev : pList->pTail;
5	pNode->pNext = pNext;
6	pNode->pPrev = pPrev;
7	pNext = pNode;
8	pPrev = pNode;
9}
10
11// nCharaNumの昇順になる位置にpNodeを挿入
12void insert(CharaList* pList, CharaNode* pNode) {
13	// 昇順になる位置を後ろから探す
14	CharaNode* pPos = pList->pTail;
15	while (pPos && pPos->nCharaNum > pNode->nCharaNum)
16		pPos = pPos->pPrev;
17	// 見つけた位置にpNodeを追加
18	add_after(pList, pPos, pNode);
19}
20
21// nCharaNumの昇順にソート
22void sort(CharaList* pList) {
23	// 中身をpCurに退避してpListを空にする
24	CharaNode* pCur = pList->pHead;
25	pList->pHead = pList->pTail = nullptr;
26	// pCurを先頭から一つずつ挿入していく
27	while (pCur) {
28		CharaNode* pNext = pCur->pNext;
29		insert(pList, pCur);
30		pCur = pNext;
31	}
32}

さらに、標準のstd::sortの真似をして比較演算子を外から渡すようにすれば、別のソート順にも対応できます。(動作検証できるように、完全なソースを載せておきます。メモリ解放は省略しています)

c++
1#include <string>
2#include <cstring>
3#include <iostream>
4using namespace std;
5
6typedef struct CharacterStatus {
7	string strName;
8	int nCharaNum;  // 登録順ソートのため
9	char chFurigana[256]; // 名前順ソートで利用する---
10	CharacterStatus* pPrev;
11	CharacterStatus* pNext;
12} CharaNode;
13
14typedef struct CharacterNodeList {
15	CharaNode* pHead;  // 先頭のノードを指すポインタ
16	CharaNode* pTail;  // 末尾のノードを指すポインタ
17} CharaList;
18
19// pPosの後ろにpNodeを追加(pPosがnullptrなら先頭に追加)
20void add_after(CharaList* pList, CharaNode* pPos, CharaNode* pNode) {
21	CharaNode*& pNext = (pPos) ? pPos->pNext : pList->pHead;
22	CharaNode*& pPrev = (pNext) ? pNext->pPrev : pList->pTail;
23	pNode->pNext = pNext;
24	pNode->pPrev = pPrev;
25	pNext = pNode;
26	pPrev = pNode;
27}
28
29// 昇順になる位置にpNodeを挿入
30template<class Compare>
31void insert(CharaList* pList, CharaNode* pNode, Compare comp) {
32	// 昇順になる位置を後ろから探す
33	CharaNode* pPos = pList->pTail;
34	while (pPos && comp(pNode, pPos))
35		pPos = pPos->pPrev;
36	// 見つけた位置にpNodeを追加
37	add_after(pList, pPos, pNode);
38}
39
40// 昇順にソート
41template<class Compare>
42void sort(CharaList* pList, Compare comp) {
43	// 中身をpCurに退避してpListを空にする
44	CharaNode* pCur = pList->pHead;
45	pList->pHead = pList->pTail = nullptr;
46	// pCurを先頭から一つずつ挿入していく
47	while (pCur) {
48		CharaNode* pNext = pCur->pNext;
49		insert(pList, pCur, comp);
50		pCur = pNext;
51	}
52}
53
54// 登録順に並び替え
55void sortListOrderRegist(CharaList* pList) {
56	sort(pList, [](CharaNode* a, CharaNode* b) { return a->nCharaNum < b->nCharaNum; });
57}
58
59// 名前順に並び替え
60void sortListOrderName(CharaList* pList) {
61	sort(pList, [](CharaNode* a, CharaNode* b) { return a->strName < b->strName; });
62}
63
64// ふりがな順に並び替え
65void sortListOrderFurigana(CharaList* pList) {
66	sort(pList, [](CharaNode* a, CharaNode* b) { return strcmp(a->chFurigana, b->chFurigana) < 0; });
67}
68
69void print(CharaList* pList) {
70	for (CharaNode* pCur = pList->pHead; pCur; pCur = pCur->pNext)
71		cout << pCur->strName << " " << pCur->nCharaNum << " " << pCur->chFurigana << ", ";
72	cout << endl;
73}
74
75int main() {
76	CharaList* pList = new CharaList{};
77	add_after(pList, nullptr, new CharaNode{ "a", 2, "え" });
78	add_after(pList, nullptr, new CharaNode{ "g", 1, "あ" });
79	add_after(pList, nullptr, new CharaNode{ "e", 4, "い" });
80	add_after(pList, nullptr, new CharaNode{ "c", 3, "う" });
81	print(pList);
82	sortListOrderName(pList);
83	print(pList);
84	sortListOrderRegist(pList);
85	print(pList);
86	sortListOrderFurigana(pList);
87	print(pList);
88}

投稿2022/06/08 13:45

編集2022/06/10 20:26

actorbug

総合スコア2224

don

2022/06/09 07:39

挿入ソートが使えるのは何となく理解できました。ありがとうございます。一応動かしてみたんですが、 add_afterの中のpNode->pNext = pNext;部分で ~pNodeがNULL~といエラーが出てしまうのですが、、、

actorbug

2022/06/09 12:42

申し訳ないですが、全体のソースコードが載っていないので、エラーを再現できません。 (こちらで試した限りでは、エラーは発生していません) 再現する最低限のコードを載せるか、それができないなら自力でデバッグしてください。

行動規範の内容に同意します

バブルソート等を用いてソートしたいってことですよね？かなり厳しいかと。一応できなくはないですが、リスト構造の良さを捨ててしまっていますよそれ。そもそも配列構造(C++でいえばstd::vectorも含む)とリスト構造の違いを理解していればありえないと思うのですが…細かい説明は省きますが、配列構造はその名の通り、配列です。なのでランダムアクセスは得意ですが、最後尾や先端とかに新しくデータを追加したり削除したりとかが苦手です。どうしても一時的に別の配列を用意してそこにコピーして削除するものは削除し、追加するなら追加する…という処理を加えてすげ替える。でもリスト構造はあの有名なイメージ(基本情報技術者試験ですら出てくる)なので、ランダムアクセスは苦手だけど、最後尾や先端とかに追加したり削除したりとかは得意。バブルソートはarr[1]とかみたいなランダムアクセスをしながら行いますよね。(多分やり方次第ではランダムアクセスしなくてもできるとは思うが、無学な俺には無理…)ということはリスト構造とは相性が悪すぎる。ランダムアクセスが苦手なものを使うわけだから。どうしてもバブルソートで行うなら、「リストからデータを取り出して、一旦配列にコピー。その配列をバブルソートで整列させて、元のリストに戻す。」と言う作業をしないといけません。無駄が多すぎます。リスト構造の良さを切り捨てていますね。それならいっそ、最初から配列構造で管理したほうがいいです。リスト構造でソート済みで管理したいだけなら、「追加時に、ソート済みになるように位置を調べてそこに追加する」でしょうか。この考え方はあるサイトさんから学んだのですが、追加時にリニアサーチで「ソート済みになるように追加位置を決める」。その後にそこに追加する。って言う感じでした。まず an = { 1, 3, 8 } に 5 を追加したい場合、まずanにあるデータ列を見て 5 をどこに追加すればソート済みになるか調べる。3 と 8 の間、つまり(0番目から考えると) 2番目に追加すればソート済みになりそうですね。ということで、この2番目に5を追加すればいい。ってことです。これを追加するときに行う。一応リスト構造は走査するためのポインタ(C++でいうiterator)がその位置にあって、行ったり来たりすることを考慮しないのならO(1)です。つまりどこに挿入しようと常に一定の時間しかかからないです。データ量がどんなに大きくとも。(ただし「どこに挿入するか」とかのチェックは考慮していない)

[修正]

すみません。修正前の回答は間違えていました…
私の知識不足が原因でした…

ご指摘を受けてよくよく考えると、バブルソートの要件には「ランダムアクセスで行う事」はありませんでしたね。

そのままやればいいかと思います。

majiponiさんがご指摘してくださったように、先端から比較して交換すればいいですね。

たとえば an = { 3, 2, 6, 1 } であれば、まず先端である 3 のところにポインタを設定し、
その次の値と比較。ポインタを pとし、条件式をp->num > p->num + 1とすると 3 > 2 となり、条件を満たしますから、
さらに別の、格納されているデータの型、つまり上記の場合はint型の変数またはポインタを用いて入れ替える。
そうすると an = { 2, 3, 6, 1 } となる。ポインタをずらして( p + 1 )、3 と 6 も同様にする。
…とやると、an = { 2, 3, 1, 6 } となるはずです。これで最大値 6 が確定。
また先端に戻って 2 と 3を比較。3と1を比較…とやり、要素数分の-1した回数行えば結果的にソートされますね。
(後から考えてやっとわかった…)

あるいはdodox86さんがご指摘してくださったように、ポインタを格納するための配列を用いて行う方法もありますね。
(流石にこれはまったく気づかなかった…)

投稿2022/06/06 23:27

編集2022/06/08 05:57

BeatStar

総合スコア4958

majiponi

2022/06/07 00:14

バブルソートは、隣り合う要素同士を比較して、「小さい」要素を前に移動させることで、ソートを実現するので、リスト構造にこだわるなら、むしろバブルソートぐらいしか選択肢はないかと。やり方ですが、 a B A b の状態から、aの後ろをAに、Aの前をa、Aの後ろをBに、Bの前をAに、Bの後ろをbに、bの前をBにすることで、 a A B b の状態にできます。

dodox86

2022/06/07 00:20

> 無駄が多すぎます。リスト構造の良さを切り捨てていますね。それならいっそ、最初から配列構造で管理したほうがいいです。実用、実務で考えるのであればそんなことは無いです。ソートに先立ってリンク、リスト構造の各要素のポインタを配列に収め、ソート時にはその配列を利用してソートの処理をし、ソートが終わったらそのポインタ配列をもとにリストのデータを並べ直すような操作はよくあります。リストに限らず、要素のサイズが大きくて並べ替えのコストが高いときに利用できる方法です。 > 一応リスト構造は走査するためのポインタ(C++でいうiterator)がその位置にあって、行ったり来たりすることを考慮しないのならO(1)です。つまりどこに挿入しようと常に一定の時間しかかからないです。あと、「行ったり来たりすることを考慮しない」と断り書きがあるものの単方向でも双方向でも、リストにおいて目的の要素を見つけるには行ったり来たりする操作は必須では？　そうであれば実質、O(n)です。O(1)として考えることに意味があるでしょうか。低評価をしたのは私ではありませんが、上記のようなことが評価の対象になっているかもしれませんし、失礼ながら現状のご回答ではその評価も理解できます。

BeatStar

2022/06/08 05:33

@ dodox86さん > 実用、実務で考えるのであればそんなことは無いです。ソートに先立ってリンク、... ああ、そういえばポインタ系の配列で行う可能性もありますね… 勉強になります… > あと、「行ったり来たりすることを考慮しない」と断り書きがあるものの単方向でも双方向でも、... ああ、確かにそうですね…

BeatStar

2022/06/08 05:37

@ majiponiさんああ、確かにバブルソートの要件に「必ずランダムアクセスで行う」とはありませんね… 固定観念でちょっと…でした…

行動規範の内容に同意します

あなたの回答