CODEWITHSUNDEEP
c++data-structureslinked-list
Ali Zahr
Ali Zahr

Reputation: 64

Bubble sorting doesnt work from the first time in the linked list

I'm trying to do bubble sorting for my linked list, it doesn't work from the first time, but if I call the function twice it sorts well, for example if the list is: 9 8 7 6 5 4 3 2 1, The sorting returns 4 3 2 1 5 6 7 8 9! What's the mistake here?

void sort() {

if(Head == NULL)
    cout << "Sorry but your list is empty! \n";
else {

    int i,j,temp,k = count();
    node *current,*nextNode;

    for(i=0; i<k-1; i++,k--) {
        current = Head;
        nextNode = current->Next;

        for(j = 1; j<k; j++) {
            if(current->item > nextNode->item){
                temp = current->item;
                current->item = nextNode->item;
                nextNode->item = temp;
            }
            current = current->Next;
            nextNode = nextNode->Next;
        }
    }
    cout << "Sorting Succeeded!\n";
}
}

Upvotes: 0

Views: 77

Answers (2)

Shashwat Kumar
Shashwat Kumar

Reputation: 5297

Do not increment i. Since j starts from 1, so i should always begin loop from 0.
Change for(i=0; i<k-1; i++,k--)
to for(i=0; i<k-1; k--)

for(i=0; i<k-1; i++,k--) should run k-1 times. But when you are incrementing i and decrementing k, then difference between i and k decreases at twice the rate, so it runs k/2 times and so only k/2 elements are sorting. And when run again, remaining k/2 elements are also sorted.

Upvotes: 1

user376507
user376507

Reputation: 2066

Change the following 2 lines

for(i=0; i<k-1; i++,k--) {

for(j = 1; j<k; j++) {

to

for(i = 0; i < (k - 1); i++) {

for(j = 0; j < (k - i - 1); j++) {

Upvotes: 0

Related Questions