How do i solve this problem Suppose a sorting algorithm in e

How do i solve this problem?

Suppose a sorting algorithm in each stage swaps only adjacent elements. That is, (like for example Bubble-Sort and Simple Insertion-Sort) in each stage it swaps A[i] and A[i + 1] for some i. Let d_i denote the the distance of A[i]. Show that A[i] must go through d_i comparisons in any algorithm of this type.

Solution

#include int main() { int array[100], n, c, d, swap; printf(\"Enter number of elements\ \"); scanf(\"%d\", &n); printf(\"Enter %d integers\ \", n); for (c = 0; c < n; c++) scanf(\"%d\", &array[c]); for (c = 0 ; c < ( n - 1 ); c++) { for (d = 0 ; d < n - c - 1; d++) { if (array[d] > array[d+1]) /* For decreasing order use < */ { swap = array[d]; array[d] = array[d+1]; array[d+1] = swap; } } } printf(\"Sorted list in ascending order:\ \"); for ( c = 0 ; c < n ; c++ ) printf(\"%d\ \", array[c]); return 0; }