Counting Inversions (Swaps) in Insertion Sort Algorithm

Subject Computer Science Data Structures and Algorithms

Question

Let A[l..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.
a) Show the insertion sort algorithm. Explain clearly how it works.
b) Modify the insertion sort algorithm to count the number of inversions in the input array.
c) Trace your algorithm for question b above as it counts the number of inversions in this array: [40, 30, 20, 10].

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

a) In pseudo-code, the Insertion Sort algorithm can be represented like below (two nested loops):

swaps=0
for j = 1 to array.size do
{aux= array[j]    //temporary variable used for swapping the compared items
//the item array[j] is inserted into sorted sub-array array[1 . . j − 1]
i = j − 1
While (i > 0) and (array[i] > aux) do
{array[i +1] = array[i]...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Arrays, Linked Lists, Queue and Stack Data Structures in C++ \$40.00
Algorithm
Array
List
Queue
Stack
Data
Structure
C++
Singly
Doubly
Prototype
Template
Function
Computer
Science
Function Asymptotic Growth & Basic Java Programming Questions \$15.00
Asymptotic
Growth Rate
Java
Main
Maryland
State
Method
Output
Class
Extends
Computer Science
Data Structures
Algorithms
Computer Engineering Questions \$4.00
Computer Science
Engineering
Intel 8086
Systems
DRAM Memory
RAS
Processors
States
Writing
Propagation
Data Paths
Time Requirements
Clocking Rate
Access Time
Computer Science - Algorithm Assignment \$25.00
Algorithm
Computer Science
Dynamic Programming
Longest Increasing Subsequence
Array
Sorting Algorithms in Java \$33.00
Computer Science
Programming
Insertion Sort
Shellsort
Heapsort
Quicksort
Input Data
Execution Time
Loops
Variables
Statements
Sequences
Functions
Java
Random Values
Input
Output
Live Chats
{"ft_lang_label":"__label__en","ft_lang_prob":0.8137517,"math_prob":0.54810464,"size":1149,"snap":"2019-43-2019-47","text_gpt3_token_len":289,"char_repetition_ratio":0.11004367,"word_repetition_ratio":0.0099502485,"special_character_ratio":0.26370758,"punctuation_ratio":0.12184874,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.982307,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-18T05:59:11Z\",\"WARC-Record-ID\":\"<urn:uuid:f4af9433-ab77-4bec-890b-e52c109adb25>\",\"Content-Length\":\"53492\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:c34deeb1-b2e1-4d19-9c02-33628b7bb630>\",\"WARC-Concurrent-To\":\"<urn:uuid:34ecd699-a7ff-4919-95fb-d3a72910b540>\",\"WARC-IP-Address\":\"52.202.27.245\",\"WARC-Target-URI\":\"https://www.24houranswers.com/college-homework-library/Computer-Science/Data-Structures-and-Algorithms/20364\",\"WARC-Payload-Digest\":\"sha1:QRB3JQCYA2DHE6Y7QYHK64X6YN7NMJFB\",\"WARC-Block-Digest\":\"sha1:72PISWNPEGULMV56JY5TUPDK2I6GLMTB\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570986677964.40_warc_CC-MAIN-20191018055014-20191018082514-00558.warc.gz\"}"}