By paradox_71, history, 9 days ago,

I recently worked on optimizing the insertion sort algorithm and wanted to share my approach with the community. This version uses a single loop to reduce the number of comparisons and swaps, making it more efficient for certain datasets.

Problem Statement Given an array of integers, sort the array in ascending order using an optimized version of the insertion sort algorithm that utilizes only one loop.

Approach The traditional insertion sort algorithm shifts elements one by one to their correct position. In my optimized version, I use a while loop to reduce the number of comparisons and swaps.

Code

My Code

Explanation 1. Input Handling: The program first takes the number of elements and the elements themselves as input. 2. Sorting Logic: • The while loop iterates through the array.

• If the current element is smaller than the previous element, they are swapped, and the index is decremented to recheck the previous elements.

• If the current element is in the correct position, the index is incremented to move to the next element.

1. Output: The sorted array is printed.

Conclusion This optimized version of insertion sort reduces the number of comparisons and swaps, making it more efficient for certain datasets. Feel free to share your thoughts or any further optimizations you might have!

• -13

 » 9 days ago, # |   +11 cool idea. not sure id call it "optimized" as it does roughly twice as many pointer movements as normal insertion sort, rather id call it "golfed"
•  » » 7 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } In some test cases it performs better then insertion sort.So i just think of calling it optimized
 » 9 days ago, # |   +17 isn't this just Gnome Sort? You ain't inventing anything new buddy
•  » » 7 days ago, # ^ |   0 Thanks for your feedback! I appreciate you pointing that out. It seems I was inspired by an existing algorithm without realizing it.
•  » » 6 days ago, # ^ |   0 i love ur pfp
 » 7 days ago, # |   +8 Please check how to format your blog! Here is a link: https://codeforces.com/blog/entry/104522
 » 6 days ago, # |   0 Auto comment: topic has been updated by paradox_71 (previous revision, new revision, compare).