Здравствуйте, Ankden.
Писал код прямо тут в приложении, так что могут быть какие нибудь глупые ошибки, но общий смысл, думаю, ясен: находим каждый элемент и ставим на своё место, при этом считая перестановки

Приложение:
int count = 0;
for (int i(0); i < N-1; i++)
if (ar[i] != i+1) {
count++
for(int j(i+1); i < N; j++)
if (ar[j] == i+1) {
int buf = ar[j];
ar[j] = ar[i];
ar[i] = buf;
}
}

Здравствуйте, Ankden.
Не совсем понятно каким боком к заданию относятся жадные алгоритмы. Если я правильно понял, то нужно посчитать минимально необходимое число обменов для сортировки произвольного массива из чисел {1, 2, 3}. Я предлагаю следующий алгоритм:
1. Подсчитать количество единиц и двоек в массиве. Этого достаточно, чтобы знать диапазоны значений в отсортированном массиве.
2. Переместить единицы на свои законные позиции, подсчитывая обмены. Если единица обменивает с двойкой, то поиск единицы нужно начинать с первой позиции, которую будут занимать двойки, если с тройкой - то с конца массива. Это гарантирует оптимальность обменов.
3. Аналогично переместить двойки на свои позиции, с поправкой на упрощение поиска.

В приложении программа, ввод/вывод сделан на C++, чистым С не владею в должной мере. Думаю, что переписать это на C не составит большого труда.

Приложение:
#include <iostream>
#include <vector>
#include <sstream>
#include <string>

int main()
{
std::vector<unsigned> a;
std::string line;

std::cout << "Please input: ";
std::getline(std::cin, line);
std::istringstream s(line.c_str());
while (!s.eof())
{
unsigned t;
s >> t;
a.push_back(t);
}

unsigned n = a.size();

int count1 = 0, count2 = 0;
for (unsigned k = 0; k < n; ++k)
{
if (a[k] == 1)
++count1;
else if (a[k] == 2)
++count2;
else if (a[k] != 3)
{
std::cout << "Wrong value in array\n";
return 1;
}
}

unsigned swap = 0;

unsigned r2 = count1;
unsigned r3 = r2 + count2;

for (unsigned k = 0; k < r2; ++k)
{
if (a[k] == 2)
{
for (unsigned j = r2; j < n; ++j)
{
if (a[j] == 1)
{
++swap;
std::cout << '(' << k << ", " << j << ')' << std::endl;
a[k] = a[j];
a[j] = 2;
break;
}
}
}
else if (a[k] == 3)
{
for (int j = n - 1; j >= r2; --j)
{
if (a[j] == 1)
{
++swap;
std::cout << '(' << k << ", " << j << ')' << std::endl;
a[k] = a[j];
a[j] = 3;
break;
}
}
}
}

for (unsigned k = r2; k < r3; ++k)
{
if (a[k] == 3)
{
for (unsigned j = r3; j < n; ++j)
{
if (a[j] == 2)
{
++swap;
std::cout << '(' << k << ", " << j << ')' << std::endl;
a[k] = 2;
a[j] = 3;
break;
}
}
}
}

std::cout << "Result array:";
for (unsigned k = 0; k < n; ++k)
{
std::cout << ' ' << a[k];
}
std::cout << std::endl;

std::cout << "Answer: " << swap << " swaps.\n";
return 0;
}