C++

Forum

 
 
Sorting a Linked List

redfury (58)
Hello, I am trying to sort a linked list. Following is my code..
First code is only of the sort function.
Second one is the complete code.
Can anyone please point out the error? The program isn't even giving the desired output. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void list::sort_list()
{
	node* temp1 = head; 
	int size = count_nodes(); 
	for (int i = 0; i < size; i++)
	{
		node* temp2 = temp1; 
		while (temp2->pnext != NULL)
		{
			if (temp2->data < temp2->pnext->data)
				swap(temp2->data, temp2->pnext->data);
			temp2 = temp2->pnext;
		}
		temp1 = temp1->pnext; 
	}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
#include <iostream>
#include <iomanip>
using namespace std;
struct node
{
	int data;
	node* pnext;
};
class list
{
public:
	node* head, * tail;
	list()
	{
		head = NULL;
		tail = NULL;
	}
	void display();
	void insert_at_the_end(int);
	void sort_list(); 
	int count_nodes(); 
};
void list::insert_at_the_end(int data)
{
	node* temp = new node;
	temp->data = data;
	temp->pnext = NULL;
	if (head == NULL)
	{
		head = temp;
		tail = temp;
	}
	else
	{
		tail->pnext = temp;
		tail = temp;
	}
	temp = NULL;
}
int list::count_nodes()
{
	int count = 0; 
	node* temp = head; 
	while (temp != NULL)
	{
		temp = temp->pnext; 
		count++; 
	}
	return count; 
}
void list::sort_list()
{
	node* temp1 = head; 
	int size = count_nodes(); 
	for (int i = 0; i < size; i++)
	{
		node* temp2 = temp1; 
		while (temp2->pnext != NULL)
		{
			if (temp2->data < temp2->pnext->data)
				swap(temp2->data, temp2->pnext->data);
			temp2 = temp2->pnext;
		}
		temp1 = temp1->pnext; 
	}
}
void list::display()
{
	node* temp = head;
	cout << "\t";
	while (temp != NULL)
	{
		cout << setw(6) << temp->data;
		temp = temp->pnext;
	}
	cout << endl;
}
int main()
{
	list obj;
	int n, num;
	cout << "Enter size of List: ";
	cin >> n;
	cout << "Enter Elements: ";
	for (int i = 1; i <= n; i++)
	{
		cin >> num;
		obj.insert_at_the_end(num);
	}
	cout << endl << endl << "List: ";
	obj.display();
	obj.sort_list(); 
	cout << endl << "New List: ";
	obj.display();
	cout << endl << endl;
	system("pause");
	return 0;
}
salem c (3700)
I suggest you start with more controlled tests.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
void test0( ) {
    cout << "Empty list\n";
    list obj;
    obj.display();
    obj.sort_list(); 
    obj.display();
}
void test1( ) {
    cout << "1-entry list\n";
    list obj;
    obj.insert_at_the_end(1);
    obj.display();
    obj.sort_list(); 
    obj.display();
}
void test2a( ) {
    cout << "2-entry list already sorted\n";
    list obj;
    for ( int i = 1 ; i <= 2 ; i++ ) {
        obj.insert_at_the_end(i);
    }
    obj.display();
    obj.sort_list(); 
    obj.display();
}
void test2b( ) {
    cout << "2-entry list unsorted\n";
    list obj;
    for ( int i = 2 ; i >= 1 ; i-- ) {
        obj.insert_at_the_end(i);
    }
    obj.display();
    obj.sort_list(); 
    obj.display();
}

int main() {
    test0();
    test1();
    test2a();
    test2b();
}

There's no point manually entering 20 numbers if it crashes on an empty list.

Figure out the first trivial case that it barfs on.

Then use the debugger to single-step the code on that failing case, and figure out the code execution path that you didn't expect.

When expectation != reality, you found a bug.
Whether that bug is in your code or between your ears (because you failed to understand the problem), that's for you to decide.

ne555 (10692)
bubble-sort for a linked list and you end up swapping the data...
whatever.

> Figure out the first trivial case that it barfs on.
here you are 
3
2 1 3
(largest element at the end, list bigger than 2)

by the way, ¿do you want ascendent or descendent order?
Topic archived. No new replies allowed.