Restore the original array after Bubble Sort

[Soham1087]

If the given array is [5, 8, 1, 9], after bubble sort, the sorted array will be [1, 5, 8, 9].

Is there a way to restore the original array [5, 8, 1, 9] using the sorted [1, 5, 8, 9]?

Do we have any algorithm for this?

I have tried this

Code: Select all

#include <iostream>
#include <algorithm>

int main()
{
    int test[] = { 5,8,1,9 };
    int index[] = { 0,1,2,3 };
    //...
    // perform bubble sort on the data in ascending order
    // utilizing the index array as a guide   
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 3; ++j) 
        {  
            // Note the test with respect to the index 
            if (test[index[j]] > test[index[j+1]])
                // exchange the indices if item is out-of-order  
                std::swap(index[j], index[j+1]);
        }
    }

    // Output results 
    std::cout << "sorted: ";

    // Print the sorted array
    for (int i = 0; i < 4; ++i)
        std::cout << test[index[i]] << " ";

   // Print the original array
    std::cout << "\noriginal: ";
    for (int i = 0; i < 4; ++i)
        std::cout << test[i] << " ";
}

Output:

Code: Select all

sorted: 1 5 8 9 
original: 5 8 1 9 

Reference - wiki, Scaler

[Roberthh]

Is there a way to restore the original array [5, 8, 1, 9] using the sorted [1, 5, 8, 9]?

No, you cannot, since the old content is overwritten and the information about the previous order is lost.

[scruss]

If you need to step through a list in order without changing it, sorted() will do that:

Code: Select all

arr = [5, 8, 1, 9]
print("Before: ", arr)
print("Step through list in order ...")
for i in sorted(arr):
    print(i)
print("After : ", arr)
print("Sort array in place (destructive) ...")
arr.sort()
print("Sorted: ", arr)

Output:

Code: Select all

Before:  [5, 8, 1, 9]
Step through list in order ...
1
5
8
9
After :  [5, 8, 1, 9]
Sort array in place (destructive) ...
Sorted:  [1, 5, 8, 9]

.sort() is a little more efficient than a bubble sort

[pythoncoder]

...
.sort() is a little more efficient than a bubble sort

That is the understatement of the year Bubble sort is notoriously slow. Its only merit is that the algorithm is easy to understand.