Объяснение алгоритмов сортировки с примерами на python

Базовый алгоритм

Mergesort является двойственным к быстрой сортировке и относится к классу алгоритмов «Разделяй и властвуй». Основной функцией этого алгоритма является функция слияния, которая получает на вход два отсортированных массива и возвращает их отсортированное объединение. В простейшем варианте её можно записать так:

Имея такую функцию можно построить функцию сортировки двумя путями.

Top-Down и Bottom-Up

Например, можно поступить как в быстрой сортировке: делить массив пополам до тех пор, пока не получатся подмассивы длины \(1\). Такие подмассивы всегда отсортированы, поэтому к ним можно применить функцию слияния:

Конечно, в отличии от быстрой сортировки, глубина стека этой рекурсивной реализации гарантированно будет \(\log n\), но можно решить эту задачу вообще не используя рекурсию.

То есть пойти снизу вверх, от одноэлементных массивов через массивы длинны \(k = 2^j\) до тех пор, пока сливаемая часть не будет содержать весь исходный массив.

Эти два подхода к решению задачи, как не трудно догадаться, носят названия Top-Down (сверху вниз) и Bottom-Up (снизу вверх). Подход сверху вниз обычно является рекурсивным. Но, если для какого-то алгоритма есть решение рекурсивное и нерекурсивное, однозначно никогда не нужно использовать рекурсивное. Собственно и здесь рекурсивное решение приведено исключительно как дань уважения быстрой сортировке.

В текущей реализации получаем следующие оценки сложности:

Sorted	Random	Reversed
\(O(n\log n)\)	\(O(n\log n)\)	\(O(n\log n)\)

И по памяти: \(S(n) = 2n\).

Реализация

Сортировка массивов

Быстрая сортировка является естественным рекурсивным алгоритмом — разделите входной массив на меньшие массивы, переместите элементы в нужную сторону оси и повторите.

При этом мы будем использовать две функции — partition() и quick_sort().

Давайте начнем с функции partition():

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array <= array:
            pivot += 1
            array, array = array, array
    array, array = array, array
    return pivot

И, наконец, давайте реализуем функцию quick_sort():

def quick_sort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

После того, как обе функции реализованы, мы можем запустить quick_sort():

array = 

quick_sort(array)
print(array)

Результат:

Поскольку алгоритм unstable (нестабилен), нет никакой гарантии, что два 19 будут всегда в этом порядке друг за другом. Хотя это ничего не значит для массива целых чисел.

Оптимизация быстрой сортировки

Учитывая, что быстрая сортировка сортирует «половинки» заданного массива независимо друг от друга, это оказывается очень удобным для распараллеливания. У нас может быть отдельный поток, который сортирует каждую «половину» массива, и в идеале мы могли бы вдвое сократить время, необходимое для его сортировки.

Однако быстрая сортировка может иметь очень глубокий рекурсивный стек вызовов, если нам особенно не повезло в выборе опорного элемента, а распараллеливание будет не так эффективно, как в случае сортировки слиянием.

Для сортировки небольших массивов рекомендуется использовать простой нерекурсивный алгоритм. Даже что-то простое, например сортировка вставкой, будет более эффективным для небольших массивов, чем быстрая сортировка. Поэтому в идеале мы могли бы проверить, имеет ли наш подмассив лишь небольшое количество элементов (большинство рекомендаций говорят о 10 или менее значений), и если да, то мы бы отсортировали его с помощью Insertion Sort (сортировка вставкой).

Как работает Быстрая сортировка

Быстрая сортировка чаще всего не сможет разделить массив на равные части. Это потому, что весь процесс зависит от того, как мы выбираем опорный элемент. Нам нужно выбрать опору так, чтобы она была примерно больше половины элементов и, следовательно, примерно меньше, чем другая половина элементов. Каким бы интуитивным ни казался этот процесс, это очень сложно сделать.

Подумайте об этом на мгновение — как бы вы выбрали адекватную опору для вашего массива? В истории быстрой сортировки было представлено много идей о том, как выбрать центральную точку — случайный выбор элемента, который не работает из-за того, что «дорогой» выбор случайного элемента не гарантирует хорошего выбора центральной точки; выбор элемента из середины; выбор медианы первого, среднего и последнего элемента; и еще более сложные рекурсивные формулы.

Самый простой подход — просто выбрать первый (или последний) элемент. По иронии судьбы, это приводит к быстрой сортировке на уже отсортированных (или почти отсортированных) массивах.

Именно так большинство людей выбирают реализацию быстрой сортировки, и, так как это просто и этот способ выбора опоры является очень эффективной операцией, и это именно то, что мы будем делать.

Теперь, когда мы выбрали опорный элемент — что нам с ним делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу опору, указатель на «меньшие» элементы и указатель на «более крупные» элементы.

Цель состоит в том, чтобы переместить элементы так, чтобы все элементы, меньшие, чем опора, находились слева от него, а все более крупные элементы были справа от него. Меньшие и большие элементы не обязательно будут отсортированы, мы просто хотим, чтобы они находились на правильной стороне оси. Затем мы рекурсивно проходим левую и правую сторону оси.

Рассмотрим пошагово то, что мы планируем сделать, это поможет проиллюстрировать весь процесс. Пусть у нас будет следующий список.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)

Выберем первый элемент как опору 29), а указатель на меньшие элементы (называемый «low») будет следующим элементом, указатель на более крупные элементы (называемый «high») станем последний элемент в списке.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

Мы двигаемся в сторону high то есть влево, пока не найдем значение, которое ниже нашего опорного элемента.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

• Теперь, когда наш элемент high указывает на элемент 21, то есть на значение меньше чем опорное значение, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет смысла менять местами значение, которое меньше, чем опорное значение, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который будет больше.
• Мы перемещаем переменную low вправо, пока не найдем элемент больше, чем опорное значение. К счастью, low уже имеет значение 89.
• Мы меняем местами low и high:

29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44

• Сразу после этого мы перемещает high влево и low вправо (поскольку 21 и 89 теперь на своих местах)
• Опять же, мы двигаемся high влево, пока не достигнем значения, меньшего, чем опорное значение, и мы сразу находим — 12
• Теперь мы ищем значение больше, чем опорное значение, двигая low вправо, и находим такое значение 41

Этот процесс продолжается до тех пор, пока указатели low и high наконец не встретятся в одном элементе:

29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,41,99,44

Мы больше не используем это опорное значение, поэтому остается только поменять опорную точку и high, и мы закончили с этим рекурсивным шагом:

28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44

Как видите, мы достигли того, что все значения, меньшие 29, теперь слева от 29, а все значения больше 29 справа.

Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 44,78,87,66,31,76,58,88,83,97,41,99,44 (правая сторона). И так далее.

Копирование

Возможно несколькими способами.

Копирование массива путем итерации массива

Первый способ — это перебрать массив и скопировать каждое значение исходного массива в целевой массив. Вот как выглядит копирование массива с использованием этого метода:

int[] source = new int;
int[] dest   = new int;

for(int i=0; i < source.length; i++) {
    source = i;
}

for(int i=0; i < source.length; i++) {
    dest = source;
}

Первые два массива int созданы. Во-вторых, исходный массив инициализируется значениями от 0 до 9 (от 0 до длины массива минус 1). В-третьих, каждый элемент в исходном массиве копируется в целевой массив.

Копирование с помощью Arrays.copyOf()

Вот как выглядит копирование массива:

int[] source = new int;

for(int i=0; i < source.length; i++) {
    source = i;
}

int[] dest = Arrays.copyOf(source, source.length);

Метод Arrays.copyOf() принимает 2 параметра. Первый — это массив для копирования. Второй — это длина нового массива — можно использовать для указания количества копируемых элементов из исходного массива.

Копирование с использованием Arrays.copyOfRange()

Метод Arrays.copyOfRange() копирует диапазон массива, не обязательно полный массив. Процесс копирования с ним:

int[] source = new int;

for(int i=0; i < source.length; i++) {
    source = i;
}

int[] dest = Arrays.copyOfRange(source, 0, source.length);

Метод Arrays.copyOfRange() принимает 3 параметра. Первый — это массив для копирования. Второй  — это первый индекс в исходном массиве, который нужно включить в копию. Третий  — это последний индекс в исходном массиве, который будет включен в копию (исключено — поэтому передача 10 будет копировать до и включая индекс 9).

Эффективная сортировка

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»)

Пирамидальная сортировка является методом сортировки, который интерпретирует элементы в массиве, как почти полное бинарное дерево.
Она берет элементы массива и вставляет их в пирамиду.
После построения пирамиды, из нее по очереди удаляются наибольшие элементы и вставляются в конец массива, где и находятся в отсортированном виде.
Общее время сортировки расчитывается по O(N logN) для N элементов.

package com.topjavatutorial;
 
public class ExampleHeapSort {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] numbers = { 12, 2, 15, 56, 23, 78, 45, 34, 16, 91, 53, 27 };
        heapsort(numbers);
        for (int h = 0; h < numbers.length; h++)
            System.out.print(numbers+ " ");
    }
 
    // sort num to num
    public static void heapsort(int[] a) {
        for (int i = a.length / 2 - 1; i >= 0; i--)
            // convert the array to a heap
            shiftDown(a, i, a.length);
        for (int i = a.length - 1; i > 0; i--) {
            swap(a, 0, i); /* deleteMax */
            shiftDown(a, 0, i);
        }
    } // end heapSort
 
    private static void shiftDown(int[] a, int i, int n) {
        int child;
        int tmp;
 
        for (tmp = a; leftChild(i) < n; i = child) {
            child = leftChild(i);
            if (child != n - 1 && (a < a))
                child++;
            if (tmp < a)
                a = a;
            else
                break;
        }
        a = tmp;
    }
 
    private static int leftChild(int i) {
        return 2 * i + 1;
    }
 
    // swap numbers
    public static void swap(int[] numbers, int i, int j) {
        int temp = numbers;
        numbers = numbers;
        numbers = temp;
    }
 
} // end class ExampleHeapSort

Вывод: 2 12 15 16 23 27 34 45 53 56 78 91

Сортировка слиянием

Сортировка слияние один из наиболее популярных алгоритмов в Java так как использует наименьшее количество сравнений.
Сортировка слиянием используется в стандартных Java библиотеках для сортировки generic.
Идеей сортировки слиянием является то, что происходит слияние двух отсортированных списков.
Сортировка слиянием занимает O(nlogn).

Высокоуровневое представление о сортировке слиянием:

Start merge sort
   sort first half (recursive)
   sort second half(recursive)
   merge sorted halves into one sorted list
End sort

Сортировка слиянием в Java:

package com.topjavatutorial;
 
public class ExampleMergeSort {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] num = { 3,6,1,7,2,8,10,4,9,5};
        int n = num.length;
        
        mergeSort(num, 0, n - 1);
        
        for (int h = 0; h < n; h++)
            System.out.print(num+ " ");
    }
 
    /*
     * Internal method that makes recursive calls to sort the data
     * elements is the array of elements to be sorted
     * low is the left most position of the array
     * high is the right most position of the array
     */
    public static void mergeSort(int[] elements, int low, int high) {
        if (low < high) { // list contains at least 2 elements
            int mid = (low + high) / 2; 
            mergeSort(elements, low, mid); // recursion : sort first half
            mergeSort(elements, mid + 1, high); // recursion : sort second half
            merge(elements, low, mid, high); // merge both sorted halves
        }
    }
 
    /*
     * Merge sorted array of elements from low to mid and mid+1
     * low is the left most position of the subset of elements
     * high is the right most position of the subset of elements
     */
    private static void merge(int[] subset, int low, int mid, int high) {
 
        int n = high-low+1;
        int[] Temp = new int;
        
        int i = low, j = mid + 1;
        int k = 0;
        
        while (i <= mid || j <= high) {
            if (i > mid)
                Temp = subset;
            else if (j > high)
                Temp = subset;
            else if (subset < subset)
                Temp = subset;
            else
                Temp = subset;
        }
        for (j = 0; j < n; j++)
            subset = Temp;
    } // end merge
}

Вывод: 1 2 3 4 5 6 7 8 9 10

Быстрая сортировка

Быстрая сортировка это алгоритм быстрой сортировки. Его среднее время O(N logN), наихудшее O(N²).

package com.topjavatutorial;
 
public class ExampleQuickSort {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        int[] numbers = {3,6,1,7,2,8,10,4,9,5};
        int n = numbers.length;
        quicksort(numbers, 0, n-1);
        
        for (int h = 0; h < n; h++)
            System.out.print(numbers+ " ");
    }
 
    // Quick sort algorithm
    public static void quicksort(int[] numbers, int low, int high) {
        if (low < high) {
            int dp = partition(numbers, low, high);
            quicksort(numbers, low, dp-1);
            quicksort(numbers, dp+1, high);
            }
    }
    
 
    // partition numbers to numbers using numbers as the pivot
    private static int partition(int[] numbers, int low, int high) {
        int pivot = numbers;
        int i = low;
        for (int j = low + 1; j <= high; j++)
        if (numbers < pivot) {
        ++i;
        swap(numbers, i, j);
        }
        //end for
        swap(numbers, low, i);
        return i; 
    } 
 
    // Exchange list and list values
    private static void swap(int[] list, int i, int j) {
        int temp = list;
        list = list;
        list = temp;
    }
}

Вывод: 1 2 3 4 5 6 7 8 9 10

Итерации

Вы можете выполнить итерацию списка несколькими различными способами. Три наиболее распространенных способа:

• Использование итератора
• Использование цикла for-each
• Использование цикла for
• Использование API Java Stream

Итерация списка с помощью итератора

Первый способ итерации списка — использовать итератор Java.

List list = new ArrayList();

list.add("first");
list.add("second");
list.add("third");

Iterator iterator = list.iterator();
while(iterator.hasNext()) {
    Object next = iterator.next();
}

Вызывая метод iterator () интерфейса List.

Вызов hasNext () выполняется внутри цикла while.

Внутри цикла while вы вызываете метод Iterator next () для получения следующего элемента, на который указывает Iterator.

Если список задан с использованием Java Generics, вы можете сохранить некоторые объекты внутри цикла while.

List<String> list = new ArrayList<>();

list.add("first");
list.add("second");
list.add("third");
    
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
    String obj = iterator.next();
}

Итерация списка с использованием цикла For-Each

Второй способ итерации List — использовать цикл for.

List list = new ArrayList();

list.add("first");
list.add("second");
list.add("third");

for(Object element : list) {
    System.out.println(element);
}

Цикл for выполняется один раз для каждого элемента. Внутри цикла for каждый элемент, в свою очередь, связан с переменной obj.

Можно изменить тип переменной внутри цикла for.

List<String> list = new ArrayList<String>();

//add elements to list

for(String element : list) {
    System.out.println(element);
}

Итерация списка с помощью цикла For

Третий способ итерации List — использовать стандартный цикл for, подобный следующему:

List list = new ArrayList();

list.add("first");
list.add("second");
list.add("third");
    
for(int i=0; i < list.size(); i++) {
    Object element = list.get(i);
}

Цикл for создает переменную int и инициализирует ее 0. Затем она зацикливается, пока переменная int i меньше размера списка. Для каждой итерации переменная i увеличивается.

Внутри цикла for обращаемся к элементам List с помощью метода get (), передавая в качестве параметра переменную i.

Опять же, если список напечатан с использованием Java Generics, например, для для строки, то вы можете использовать универсальный тип списка в качестве типа для локальной переменной, которая присваивается каждому элементу списка во время итерации.

List<String> list = new ArrayList<String>();

list.add("first");
list.add("second");
list.add("third");
    
for(int i=0; i < list.size(); i++) {
    String element = list.get(i);
}

Тип локальной переменной внутри цикла for теперь String. Поскольку список обычно типизируется как String, он может содержать только объекты String.

Следовательно, компилятор знает, что только метод String может быть возвращен из метода get (). Поэтому вам не нужно приводить элемент, возвращенный get (), в String.

Перебор списка с использованием API Java Stream

Четвертый способ итерации через API Java Stream. Для итерации вы должны сначала получить поток из списка. Получение потока из списка в Java выполняется путем вызова метода Liststream ().

List<String> stringList = new ArrayList<String>();

stringList.add("abc");
stringList.add("def");

Stream<String> stream = stringList.stream();

Как только вы получили поток из списка, вы можете выполнить итерацию потока, вызвав его метод forEach ().

List<String> stringList = new ArrayList<String>();

stringList.add("one");
stringList.add("two");
stringList.add("three");

Stream<String> stream = stringList.stream();
stream
    .forEach( element -> { System.out.println(element); });

Вызов метода forEach () заставит Stream выполнить внутреннюю итерацию всех элементов потока.

Оцени статью

Оценить

Средняя оценка / 5. Количество голосов:

Видим, что вы не нашли ответ на свой вопрос.

Помогите улучшить статью.

Спасибо за ваши отзыв!

Адаптация алгоритма для сортировки

• Вся возня с буфером обмена и его последующее слияние с массивом нужны только если в массиве в самом деле не было свободного места. Если мы сливаем фрагменты длиной A и B, а после них есть еще хотя бы S ячеек неотсортированного пространства, то нам достаточно разбить массивы на куски, отсортировать их и слить. Особенно эффективно это будет работать, если S=A=B.
• Надо постараться, чтобы длина остатка была нулевой, а граница между отсортированными фрагментами попала точно на границу кусков длины S. Проще всего этого добиться, если выбрать S равным степени двойки, а A и B заставить делиться на него.
• Сортировка кусков массивов требует ((A+B)/S)2/2 сравнений. Последующая сортировка буфера обмена – O(S*log( S )) сравнений. Поэтому выбирать S близким к sqrt(N) не обязательно, можно увеличить его, например, до N/log(N).

алгоритм примерно в сотню строк8выигрываетRRRUPD:

Implementing Merge Sort Algorithm

Below we have a C program implementing merge sort algorithm.

Given array:
32 45 67 2 7
Sorted array:
2 7 32 45 67

Complexity Analysis of Merge Sort

Merge Sort is quite fast, and has a time complexity of . It is also a stable sort, which means the «equal» elements are ordered in the same order in the sorted list.

In this section we will understand why the running time for merge sort is .

As we have already learned in Binary Search that whenever we divide a number into half in every step, it can be represented using a logarithmic function, which is and the number of steps can be represented by (at most)

Also, we perform a single step operation to find out the middle of any subarray, i.e. .

And to merge the subarrays, made by dividing the original array of elements, a running time of will be required.

Hence the total time for function will become , which gives us a time complexity of .

Worst Case Time Complexity : O(n*log n)

Best Case Time Complexity : O(n*log n)

Average Time Complexity : O(n*log n)

Space Complexity: O(n)

• Time complexity of Merge Sort is in all the 3 cases (worst, average and best) as merge sort always divides the array in two halves and takes linear time to merge two halves.
• It requires equal amount of additional space as the unsorted array. Hence its not at all recommended for searching large unsorted arrays.
• It is the best Sorting technique used for sorting Linked Lists.

• ← Prev
• Next →

Divide and Conquer Strategy

Using the Divide and Conquer technique, we divide a problem into subproblems. When the solution to each subproblem is ready, we ‘combine’ the results from the subproblems to solve the main problem.

Suppose we had to sort an array A. A subproblem would be to sort a sub-section of this array starting at index p and ending at index r, denoted as A.

Divide
If q is the half-way point between p and r, then we can split the subarray A into two arrays A and A.

Conquer
In the conquer step, we try to sort both the subarrays A and A. If we haven’t yet reached the base case, we again divide both these subarrays and try to sort them.

Combine
When the conquer step reaches the base step and we get two sorted subarrays A and A for array A, we combine the results by creating a sorted array A from two sorted subarrays A and A.

Не спеша, эффективно и правильно – путь разработки. Часть 3. Практика

Черновой вариант книги Никиты Зайцева, a.k.a.WildHare. Разработкой на платформе 1С автор занимается с 1996-го года, специализация — большие и по-хорошему страшные системы. Квалификация “Эксперт”, несколько успешных проектов класса “сверхтяжелая”. Успешные проекты ЦКТП. Четыре года работал в самой “1С”, из них два с половиной архитектором и ведущим разработчиком облачной Технологии 1cFresh. Ну — и так далее. Не хвастовства ради, а понимания для. Текст написан не фантазером-теоретиком, а экспертом, у которого за плечами почти двадцать три года инженерной практики на больших проектах.

Delphi (сортировка произвольных типов данных — простое слияние)

unit uMergeSort;
 
interface
type
  TItem = Integer;               //Здесь можно написать Ваш произвольный тип
  TArray = array of TItem;
 
  procedure MergeSort(var Arr: TArray);
 
implementation
 
function IsBigger(d1, d2 : TItem) : Boolean;
begin
  Result := (d1 > d2);     //Сравниваем d1 и d2. Не обязательно так. Зависит от Вашего типа.
  //Сюда можно добавить счетчик сравнений
end;
 
//Процедура сортировки слияниями
procedure MergeSort(var Arr: TArray);
var
  tmp : TArray; //Временный буфер
  //Слияние
  procedure merge(L, Spl, R : Integer);
  var
    i, j, k : Integer;
  begin
    i := L;
    j := Spl + 1;
    k := 0;
    //Выбираем меньший из первых и добавляем в tmp
    while (i <= Spl) and (j <=R) do
    begin
      if IsBigger(Arr, Arr) then
      begin
        tmp := Arr;
        Inc(j);
      end
      else
      begin
        tmp := Arr;
        Inc(i);
      end;
      Inc(k);
    end;
    //Просто дописываем в tmp оставшиеся эл-ты
    if i <= Spl then      //Если первая часть не пуста
      for j := i to Spl do
      begin
        tmp := Arr;
        Inc(k);
      end
    else                  //Если вторая часть не пуста
      for i := j to R do
      begin
        tmp := Arr;
        Inc(k);
      end;
    //Перемещаем из tmp в arr
    Move(tmp, Arr, k*SizeOf(TItem));
  end;
 
  //Сортировка
  procedure sort(L, R : Integer);
  var
    splitter : Integer;
  begin
    //Массив из 1-го эл-та упорядочен по определению
    if L >= R then Exit;
    splitter := (L + R) div 2;  //Делим массив пополам
    sort(L, splitter);          //Сортируем каждую
    sort(splitter + 1, R);      //часть по отдельности
    merge(L, splitter, R);      //Производим слияние
  end;
 
  //Основная часть процедуры сортировки
begin
  SetLength(tmp, Length(Arr));
  sort(0, Length(Arr) - 1);
  SetLength(tmp, 0);
end;
 
end.

Пример 1: сортировка ArrayList

Здесь мы сортируем ArrayList типа String. Делать это можно, просто используя метод Collections.sort (arraylist). Список вывода будет отсортирован по алфавиту.

import java.util.*;  public class Details  
{    	public static void main(String args[]){
  	   ArrayList listofcountries = new ArrayList();
  	   listofcountries.add("India");
  	   listofcountries.add("US");
  	   listofcountries.add("China");
  	   listofcountries.add("Denmark");
    	   /*Unsorted List*/  	   System.out.println("До:");
  	   for(String counter: listofcountries){
  			System.out.println(counter);
  		}    	   /* Sort statement*/
  	   Collections.sort(listofcountries);
    	   /* Sorted List*/ 
 	   System.out.println("После:");
  	   for(String counter: listofcountries){
  			System.out.println(counter);
  		} 
}  
}

Выход:

До:  India  US  China  Denmark  
После:  China  Denmark  India  US